YES
Input TRS:
      1: a__fib(N) -> a__sel(mark(N),a__fib1(s(0()),s(0())))
      2: a__fib1(X,Y) -> cons(mark(X),fib1(Y,add(X,Y)))
      3: a__add(0(),X) -> mark(X)
      4: a__add(s(X),Y) -> s(a__add(mark(X),mark(Y)))
      5: a__sel(0(),cons(X,XS)) -> mark(X)
      6: a__sel(s(N),cons(X,XS)) -> a__sel(mark(N),mark(XS))
      7: mark(fib(X)) -> a__fib(mark(X))
      8: mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2))
      9: mark(fib1(X1,X2)) -> a__fib1(mark(X1),mark(X2))
      10: mark(add(X1,X2)) -> a__add(mark(X1),mark(X2))
      11: mark(s(X)) -> s(mark(X))
      12: mark(0()) -> 0()
      13: mark(cons(X1,X2)) -> cons(mark(X1),X2)
      14: a__fib(X) -> fib(X)
      15: a__sel(X1,X2) -> sel(X1,X2)
      16: a__fib1(X1,X2) -> fib1(X1,X2)
      17: a__add(X1,X2) -> add(X1,X2)
Number of strict rules: 17
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #a__fib1(X,Y) -> #mark(X)
     #2: #a__sel(s(N),cons(X,XS)) -> #a__sel(mark(N),mark(XS))
     #3: #a__sel(s(N),cons(X,XS)) -> #mark(N)
     #4: #a__sel(s(N),cons(X,XS)) -> #mark(XS)
     #5: #mark(cons(X1,X2)) -> #mark(X1)
     #6: #mark(fib1(X1,X2)) -> #a__fib1(mark(X1),mark(X2))
     #7: #mark(fib1(X1,X2)) -> #mark(X1)
     #8: #mark(fib1(X1,X2)) -> #mark(X2)
     #9: #mark(s(X)) -> #mark(X)
     #10: #mark(fib(X)) -> #a__fib(mark(X))
     #11: #mark(fib(X)) -> #mark(X)
     #12: #mark(add(X1,X2)) -> #a__add(mark(X1),mark(X2))
     #13: #mark(add(X1,X2)) -> #mark(X1)
     #14: #mark(add(X1,X2)) -> #mark(X2)
     #15: #a__sel(0(),cons(X,XS)) -> #mark(X)
     #16: #a__add(0(),X) -> #mark(X)
     #17: #a__fib(N) -> #a__sel(mark(N),a__fib1(s(0()),s(0())))
     #18: #a__fib(N) -> #mark(N)
     #19: #a__fib(N) -> #a__fib1(s(0()),s(0()))
     #20: #mark(sel(X1,X2)) -> #a__sel(mark(X1),mark(X2))
     #21: #mark(sel(X1,X2)) -> #mark(X1)
     #22: #mark(sel(X1,X2)) -> #mark(X2)
     #23: #a__add(s(X),Y) -> #a__add(mark(X),mark(Y))
     #24: #a__add(s(X),Y) -> #mark(X)
     #25: #a__add(s(X),Y) -> #mark(Y)
Number of SCCs: 1, DPs: 25
  SCC { #1..25 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__add	w: max(x1, x2)
      a__add	w: max(x1, x2)
      #a__fib1	w: max(x1)
      fib1	w: max(x1, x2)
      fib	w: x1 + 2
      #mark	w: x1
      0 	w: 1
      sel	w: max(x1 + 1, x2)
      #a__sel	w: max(x1, x2)
      mark	w: x1
      a__sel	w: max(x1 + 1, x2)
      #a__fib	w: x1 + 1
      cons	w: max(x1, x2)
      a__fib	w: x1 + 2
      add	w: max(x1, x2)
      a__fib1	w: max(x1, x2)
    USABLE RULES: { 1..17 }
    Removed DPs: #10 #11 #18 #21
Number of SCCs: 1, DPs: 19
  SCC { #1..9 #12..16 #20 #22..25 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__add	w: max(x1 + 18458, x2 + 18458)
      a__add	w: max(x1, x2)
      #a__fib1	w: max(x1 + 18458)
      fib1	w: max(x1, x2)
      fib	w: x1 + 1325
      #mark	w: x1 + 18458
      0 	w: 1
      sel	w: max(x1 + 1325, x2)
      #a__sel	w: max(x1 + 18459, x2 + 18458)
      mark	w: x1
      a__sel	w: max(x1 + 1325, x2)
      #a__fib	w: x1 + 1
      cons	w: max(x1, x2)
      a__fib	w: x1 + 1325
      add	w: max(x1, x2)
      a__fib1	w: max(x1, x2)
    USABLE RULES: { 1..17 }
    Removed DPs: #3
Number of SCCs: 1, DPs: 18
  SCC { #1 #2 #4..9 #12..16 #20 #22..25 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__add	w: max(x1 + 18588, x2 + 18588)
      a__add	w: max(x1, x2)
      #a__fib1	w: max(x1 + 18588)
      fib1	w: max(x1, x2)
      fib	w: x1 + 39474
      #mark	w: x1 + 18588
      0 	w: 16908
      sel	w: max(x1 + 21241, x2 + 21240)
      #a__sel	w: max(x1 + 39826, x2 + 39827)
      mark	w: x1
      a__sel	w: max(x1 + 21241, x2 + 21240)
      #a__fib	w: x1 + 1
      cons	w: max(x1, x2)
      a__fib	w: x1 + 39474
      add	w: max(x1, x2)
      a__fib1	w: max(x1, x2)
    USABLE RULES: { 1..17 }
    Removed DPs: #4 #15 #20 #22
Number of SCCs: 2, DPs: 14
  SCC { #2 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      s 	s: [1]	p: 4	w: x1
      #a__add	s: [2]	p: 0	w: max(x2 + 1)
      a__add	s: [2,1]	p: 5	w: max(x1, x2)
      #a__fib1	s: 2
      fib1	s: []	p: 3	w: max(x1 + 8947, x2 + 8947)
      fib	s: []	p: 1	w: 17895
      #mark	s: []	p: 0	w: 1
      0 	s: []	p: 0	w: 1
      sel	s: []	p: 2	w: x2 + 8946
      #a__sel	s: 1
      mark	s: 1
      a__sel	s: []	p: 2	w: x2 + 8946
      #a__fib	s: []	p: 0	w: 1
      cons	s: [1]	p: 1	w: max(x1 + 8947, x2)
      a__fib	s: []	p: 1	w: 17895
      add	s: [2,1]	p: 5	w: max(x1, x2)
      a__fib1	s: []	p: 3	w: max(x1 + 8947, x2 + 8947)
    USABLE RULES: { 1..17 }
    Removed DPs: #2
Number of SCCs: 1, DPs: 13
  SCC { #1 #5..9 #12..14 #16 #23..25 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__add	w: max(x1 + 13359, x2 + 13359)
      a__add	w: max(x1, x2)
      #a__fib1	w: max(x1 + 13360)
      fib1	w: max(x1 + 4188, x2 + 4188)
      fib	w: x1 + 35931
      #mark	w: x1 + 13359
      0 	w: 1
      sel	w: max(x1 + 31742, x2 + 31742)
      #a__sel	w: 0
      mark	w: x1
      a__sel	w: max(x1 + 31742, x2 + 31742)
      #a__fib	w: 1
      cons	w: max(x1 + 1, x2)
      a__fib	w: x1 + 35931
      add	w: max(x1, x2)
      a__fib1	w: max(x1 + 4188, x2 + 4188)
    USABLE RULES: { 1..17 }
    Removed DPs: #1 #5..8
Number of SCCs: 1, DPs: 8
  SCC { #9 #12..14 #16 #23..25 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      s 	s: [1]	p: 4	w: x1
      #a__add	s: [1,2]	p: 6	w: max(x1, x2)
      a__add	s: [2,1]	p: 7	w: max(x1, x2)
      #a__fib1	s: 2
      fib1	s: []	p: 3	w: max(x1 + 2, x2 + 2)
      fib	s: []	p: 1	w: 5
      #mark	s: [1]	p: 5	w: x1
      0 	s: []	p: 0	w: 1
      sel	s: []	p: 2	w: x2 + 1
      #a__sel	s: 1
      mark	s: 1
      a__sel	s: []	p: 2	w: x2 + 1
      #a__fib	s: []	p: 0	w: 1
      cons	s: [1]	p: 1	w: max(x1 + 2, x2)
      a__fib	s: []	p: 1	w: 5
      add	s: [2,1]	p: 7	w: max(x1, x2)
      a__fib1	s: []	p: 3	w: max(x1 + 2, x2 + 2)
    USABLE RULES: { 1..17 }
    Removed DPs: #9 #12..14 #16 #23..25
Number of SCCs: 0, DPs: 0