YES
Input TRS:
      1: a__terms(N) -> cons(recip(a__sqr(mark(N))),terms(s(N)))
      2: a__sqr(0()) -> 0()
      3: a__sqr(s(X)) -> s(a__add(a__sqr(mark(X)),a__dbl(mark(X))))
      4: a__dbl(0()) -> 0()
      5: a__dbl(s(X)) -> s(s(a__dbl(mark(X))))
      6: a__add(0(),X) -> mark(X)
      7: a__add(s(X),Y) -> s(a__add(mark(X),mark(Y)))
      8: a__first(0(),X) -> nil()
      9: a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z))
      10: a__half(0()) -> 0()
      11: a__half(s(0())) -> 0()
      12: a__half(s(s(X))) -> s(a__half(mark(X)))
      13: a__half(dbl(X)) -> mark(X)
      14: mark(terms(X)) -> a__terms(mark(X))
      15: mark(sqr(X)) -> a__sqr(mark(X))
      16: mark(add(X1,X2)) -> a__add(mark(X1),mark(X2))
      17: mark(dbl(X)) -> a__dbl(mark(X))
      18: mark(first(X1,X2)) -> a__first(mark(X1),mark(X2))
      19: mark(half(X)) -> a__half(mark(X))
      20: mark(cons(X1,X2)) -> cons(mark(X1),X2)
      21: mark(recip(X)) -> recip(mark(X))
      22: mark(s(X)) -> s(mark(X))
      23: mark(0()) -> 0()
      24: mark(nil()) -> nil()
      25: a__terms(X) -> terms(X)
      26: a__sqr(X) -> sqr(X)
      27: a__add(X1,X2) -> add(X1,X2)
      28: a__dbl(X) -> dbl(X)
      29: a__first(X1,X2) -> first(X1,X2)
      30: a__half(X) -> half(X)
Number of strict rules: 30
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #a__add(0(),X) -> #mark(X)
     #2: #a__half(dbl(X)) -> #mark(X)
     #3: #a__first(s(X),cons(Y,Z)) -> #mark(Y)
     #4: #a__half(s(s(X))) -> #a__half(mark(X))
     #5: #a__half(s(s(X))) -> #mark(X)
     #6: #mark(terms(X)) -> #a__terms(mark(X))
     #7: #mark(terms(X)) -> #mark(X)
     #8: #mark(cons(X1,X2)) -> #mark(X1)
     #9: #a__add(s(X),Y) -> #a__add(mark(X),mark(Y))
     #10: #a__add(s(X),Y) -> #mark(X)
     #11: #a__add(s(X),Y) -> #mark(Y)
     #12: #a__dbl(s(X)) -> #a__dbl(mark(X))
     #13: #a__dbl(s(X)) -> #mark(X)
     #14: #mark(s(X)) -> #mark(X)
     #15: #mark(dbl(X)) -> #a__dbl(mark(X))
     #16: #mark(dbl(X)) -> #mark(X)
     #17: #mark(half(X)) -> #a__half(mark(X))
     #18: #mark(half(X)) -> #mark(X)
     #19: #mark(recip(X)) -> #mark(X)
     #20: #mark(add(X1,X2)) -> #a__add(mark(X1),mark(X2))
     #21: #mark(add(X1,X2)) -> #mark(X1)
     #22: #mark(add(X1,X2)) -> #mark(X2)
     #23: #a__sqr(s(X)) -> #a__add(a__sqr(mark(X)),a__dbl(mark(X)))
     #24: #a__sqr(s(X)) -> #a__sqr(mark(X))
     #25: #a__sqr(s(X)) -> #mark(X)
     #26: #a__sqr(s(X)) -> #a__dbl(mark(X))
     #27: #a__sqr(s(X)) -> #mark(X)
     #28: #a__terms(N) -> #a__sqr(mark(N))
     #29: #a__terms(N) -> #mark(N)
     #30: #mark(sqr(X)) -> #a__sqr(mark(X))
     #31: #mark(sqr(X)) -> #mark(X)
     #32: #mark(first(X1,X2)) -> #a__first(mark(X1),mark(X2))
     #33: #mark(first(X1,X2)) -> #mark(X1)
     #34: #mark(first(X1,X2)) -> #mark(X2)
Number of SCCs: 1, DPs: 34
  SCC { #1..34 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__first	w: max(x1 + 20205, x2 + 20203)
      recip	w: x1 + 1
      dbl	w: x1
      a__half	w: x1
      #a__add	w: max(x1 + 19335, x2 + 19335)
      a__add	w: max(x1, x2)
      a__dbl	w: x1
      #a__half	w: x1 + 19335
      a__sqr	w: x1
      half	w: x1
      #a__terms	w: x1 + 19336
      #mark	w: x1 + 19335
      0 	w: 0
      nil	w: 0
      #a__dbl	w: x1 + 19335
      mark	w: x1
      first	w: max(x1 + 870, x2 + 869)
      a__first	w: max(x1 + 870, x2 + 869)
      cons	w: max(x1 + 1)
      add	w: max(x1, x2)
      sqr	w: x1
      a__terms	w: x1 + 29535
      #a__sqr	w: x1 + 19335
      terms	w: x1 + 29535
    USABLE RULES: { 1..30 }
    Removed DPs: #3 #6..8 #19 #28 #29 #33 #34
Number of SCCs: 1, DPs: 24
  SCC { #1 #2 #4 #5 #9..18 #20..27 #30 #31 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__first	w: max(x1 + 20205, x2 + 20203)
      recip	w: x1 + 31112
      dbl	w: x1
      a__half	w: x1 + 1
      #a__add	w: max(x1 + 28163, x2 + 28163)
      a__add	w: max(x1, x2)
      a__dbl	w: x1
      #a__half	w: x1 + 28163
      a__sqr	w: x1
      half	w: x1 + 1
      #a__terms	w: x1 + 19336
      #mark	w: x1 + 28163
      0 	w: 0
      nil	w: 0
      #a__dbl	w: x1 + 28163
      mark	w: x1
      first	w: max(x1 + 2, x2 + 1)
      a__first	w: max(x1 + 2, x2 + 1)
      cons	w: max(x1 + 1)
      add	w: max(x1, x2)
      sqr	w: x1
      a__terms	w: x1 + 43325
      #a__sqr	w: x1 + 28163
      terms	w: x1 + 43325
    USABLE RULES: { 1..30 }
    Removed DPs: #17 #18
Number of SCCs: 2, DPs: 20
  SCC { #4 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      s 	s: [1]	p: 0
      #a__first	s: 2
      recip	s: []	p: 2
      dbl	s: [1]	p: 2
      a__half	s: 1
      #a__add	s: [1,2]	p: 0
      a__add	s: [2,1]	p: 1
      a__dbl	s: [1]	p: 2
      #a__half	s: 1
      a__sqr	s: [1]	p: 2
      half	s: 1
      #a__terms	s: []	p: 0
      #mark	s: []	p: 0
      0 	s: []	p: 0
      nil	s: []	p: 0
      #a__dbl	s: []	p: 0
      mark	s: 1
      first	s: []	p: 0
      a__first	s: []	p: 0
      cons	s: []	p: 0
      add	s: [2,1]	p: 1
      sqr	s: [1]	p: 2
      a__terms	s: [1]	p: 2
      #a__sqr	s: []	p: 0
      terms	s: [1]	p: 2
    USABLE RULES: { 1..30 }
    Removed DPs: #4
Number of SCCs: 1, DPs: 19
  SCC { #1 #9..16 #20..27 #30 #31 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__first	w: 0
      recip	w: 1
      dbl	w: x1 + 1
      a__half	w: x1 + 1
      #a__add	w: max(x1 + 48491, x2 + 48491)
      a__add	w: max(x1, x2)
      a__dbl	w: x1 + 1
      #a__half	w: 28163
      a__sqr	w: x1 + 1
      half	w: x1 + 1
      #a__terms	w: 19336
      #mark	w: x1 + 48491
      0 	w: 1
      nil	w: 12701
      #a__dbl	w: x1 + 48492
      mark	w: x1
      first	w: max(x1 + 46869)
      a__first	w: max(x1 + 46869)
      cons	w: 0
      add	w: max(x1, x2)
      sqr	w: x1 + 1
      a__terms	w: 49364
      #a__sqr	w: x1 + 48492
      terms	w: 49364
    USABLE RULES: { 1..30 }
    Removed DPs: #13 #16 #25 #27 #31
Number of SCCs: 2, DPs: 12
  SCC { #12 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      s 	s: [1]	p: 0
      #a__first	s: 2
      recip	s: []	p: 2
      dbl	s: [1]	p: 2
      a__half	s: 1
      #a__add	s: [1,2]	p: 0
      a__add	s: [2,1]	p: 1
      a__dbl	s: [1]	p: 2
      #a__half	s: 1
      a__sqr	s: [1]	p: 2
      half	s: 1
      #a__terms	s: []	p: 0
      #mark	s: []	p: 0
      0 	s: []	p: 0
      nil	s: []	p: 0
      #a__dbl	s: [1]	p: 0
      mark	s: 1
      first	s: []	p: 0
      a__first	s: []	p: 0
      cons	s: []	p: 0
      add	s: [2,1]	p: 1
      sqr	s: [1]	p: 2
      a__terms	s: [1]	p: 2
      #a__sqr	s: []	p: 0
      terms	s: [1]	p: 2
    USABLE RULES: { 1..30 }
    Removed DPs: #12
Number of SCCs: 1, DPs: 11
  SCC { #1 #9..11 #14 #20..24 #30 }
POLO(Sum)... POLO(max)... succeeded.
      s 	w: x1
      #a__first	w: 0
      recip	w: 1
      dbl	w: x1 + 45543
      a__half	w: x1 + 15934
      #a__add	w: max(x1 + 31490, x2 + 42985)
      a__add	w: max(x1, x2 + 11496)
      a__dbl	w: x1 + 45543
      #a__half	w: 28163
      a__sqr	w: x1 + 57039
      half	w: x1 + 15934
      #a__terms	w: 19336
      #mark	w: x1 + 31490
      0 	w: 1
      nil	w: 3
      #a__dbl	w: 48492
      mark	w: x1
      first	w: max(x1 + 2, x2 + 1)
      a__first	w: max(x1 + 2, x2 + 1)
      cons	w: 0
      add	w: max(x1, x2 + 11496)
      sqr	w: x1 + 57039
      a__terms	w: 57388
      #a__sqr	w: x1 + 88529
      terms	w: 57388
    USABLE RULES: { 1..30 }
    Removed DPs: #1 #11 #22
Number of SCCs: 1, DPs: 8
  SCC { #9 #10 #14 #20 #21 #23 #24 #30 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      s 	s: [1]	p: 0
      #a__first	s: 2
      recip	s: []	p: 3
      dbl	s: [1]	p: 3
      a__half	s: 1
      #a__add	s: [1,2]	p: 1
      a__add	s: [2,1]	p: 2
      a__dbl	s: [1]	p: 3
      #a__half	s: []	p: 0
      a__sqr	s: [1]	p: 4
      half	s: 1
      #a__terms	s: []	p: 0
      #mark	s: 1
      0 	s: []	p: 0
      nil	s: []	p: 0
      #a__dbl	s: []	p: 0
      mark	s: 1
      first	s: []	p: 0
      a__first	s: []	p: 0
      cons	s: []	p: 0
      add	s: [2,1]	p: 2
      sqr	s: [1]	p: 4
      a__terms	s: [1]	p: 4
      #a__sqr	s: [1]	p: 4
      terms	s: [1]	p: 4
    USABLE RULES: { 1..30 }
    Removed DPs: #10 #14 #20 #21 #23 #24
Number of SCCs: 1, DPs: 1
  SCC { #9 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      s 	s: [1]	p: 0
      #a__first	s: 2
      recip	s: []	p: 3
      dbl	s: [1]	p: 3
      a__half	s: 1
      #a__add	s: [1,2]	p: 1
      a__add	s: [2,1]	p: 2
      a__dbl	s: [1]	p: 3
      #a__half	s: []	p: 0
      a__sqr	s: [1]	p: 4
      half	s: 1
      #a__terms	s: []	p: 0
      #mark	s: 1
      0 	s: []	p: 0
      nil	s: []	p: 0
      #a__dbl	s: []	p: 0
      mark	s: 1
      first	s: []	p: 0
      a__first	s: []	p: 0
      cons	s: []	p: 0
      add	s: [2,1]	p: 2
      sqr	s: [1]	p: 4
      a__terms	s: [1]	p: 4
      #a__sqr	s: [1]	p: 4
      terms	s: [1]	p: 4
    USABLE RULES: { 1..30 }
    Removed DPs: #9
Number of SCCs: 0, DPs: 0