YES
Input TRS:
      1: a__nats() -> a__adx(a__zeros())
      2: a__zeros() -> cons(0(),zeros())
      3: a__incr(cons(X,Y)) -> cons(s(X),incr(Y))
      4: a__adx(cons(X,Y)) -> a__incr(cons(X,adx(Y)))
      5: a__hd(cons(X,Y)) -> mark(X)
      6: a__tl(cons(X,Y)) -> mark(Y)
      7: mark(nats()) -> a__nats()
      8: mark(adx(X)) -> a__adx(mark(X))
      9: mark(zeros()) -> a__zeros()
      10: mark(incr(X)) -> a__incr(mark(X))
      11: mark(hd(X)) -> a__hd(mark(X))
      12: mark(tl(X)) -> a__tl(mark(X))
      13: mark(cons(X1,X2)) -> cons(X1,X2)
      14: mark(0()) -> 0()
      15: mark(s(X)) -> s(X)
      16: a__nats() -> nats()
      17: a__adx(X) -> adx(X)
      18: a__zeros() -> zeros()
      19: a__incr(X) -> incr(X)
      20: a__hd(X) -> hd(X)
      21: a__tl(X) -> tl(X)
Number of strict rules: 21
Direct POLO(bPol) ... removes: 18 4 15 8 1 3 16 21 19 17 5 10 7 20 14 12 11 9 13 6 2
      incr	w: x1 + 29536
      hd	w: 2 * x1 + 7
      s 	w: x1 + 29534
      a__incr	w: x1 + 59071
      a__nats	w: 146539
      adx	w: 2 * x1 + 59074
      zeros	w: 13326
      a__hd	w: 2 * x1 + 8
      0 	w: 868
      tl	w: 2 * x1 + 6885
      mark	w: 2 * x1 + 1
      a__adx	w: 2 * x1 + 118145
      nats	w: 73281
      cons	w: x1 + x2 + 1
      a__tl	w: 2 * x1 + 6886
      a__zeros	w: 14196
Number of strict rules: 0