YES
Input TRS:
      1: a__U11(tt(),N) -> mark(N)
      2: a__U21(tt(),M,N) -> s(a__plus(mark(N),mark(M)))
      3: a__U31(tt()) -> 0()
      4: a__U41(tt(),M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
      5: a__and(tt(),X) -> mark(X)
      6: a__isNat(0()) -> tt()
      7: a__isNat(plus(V1,V2)) -> a__and(a__isNat(V1),isNat(V2))
      8: a__isNat(s(V1)) -> a__isNat(V1)
      9: a__isNat(x(V1,V2)) -> a__and(a__isNat(V1),isNat(V2))
      10: a__plus(N,0()) -> a__U11(a__isNat(N),N)
      11: a__plus(N,s(M)) -> a__U21(a__and(a__isNat(M),isNat(N)),M,N)
      12: a__x(N,0()) -> a__U31(a__isNat(N))
      13: a__x(N,s(M)) -> a__U41(a__and(a__isNat(M),isNat(N)),M,N)
      14: mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
      15: mark(U21(X1,X2,X3)) -> a__U21(mark(X1),X2,X3)
      16: mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
      17: mark(U31(X)) -> a__U31(mark(X))
      18: mark(U41(X1,X2,X3)) -> a__U41(mark(X1),X2,X3)
      19: mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
      20: mark(and(X1,X2)) -> a__and(mark(X1),X2)
      21: mark(isNat(X)) -> a__isNat(X)
      22: mark(tt()) -> tt()
      23: mark(s(X)) -> s(mark(X))
      24: mark(0()) -> 0()
      25: a__U11(X1,X2) -> U11(X1,X2)
      26: a__U21(X1,X2,X3) -> U21(X1,X2,X3)
      27: a__plus(X1,X2) -> plus(X1,X2)
      28: a__U31(X) -> U31(X)
      29: a__U41(X1,X2,X3) -> U41(X1,X2,X3)
      30: a__x(X1,X2) -> x(X1,X2)
      31: a__and(X1,X2) -> and(X1,X2)
      32: a__isNat(X) -> isNat(X)
Number of strict rules: 32
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #a__U21(tt(),M,N) -> #a__plus(mark(N),mark(M))
     #2: #a__U21(tt(),M,N) -> #mark(N)
     #3: #a__U21(tt(),M,N) -> #mark(M)
     #4: #a__x(N,s(M)) -> #a__U41(a__and(a__isNat(M),isNat(N)),M,N)
     #5: #a__x(N,s(M)) -> #a__and(a__isNat(M),isNat(N))
     #6: #a__x(N,s(M)) -> #a__isNat(M)
     #7: #a__isNat(x(V1,V2)) -> #a__and(a__isNat(V1),isNat(V2))
     #8: #a__isNat(x(V1,V2)) -> #a__isNat(V1)
     #9: #a__plus(N,s(M)) -> #a__U21(a__and(a__isNat(M),isNat(N)),M,N)
     #10: #a__plus(N,s(M)) -> #a__and(a__isNat(M),isNat(N))
     #11: #a__plus(N,s(M)) -> #a__isNat(M)
     #12: #mark(s(X)) -> #mark(X)
     #13: #a__x(N,0()) -> #a__U31(a__isNat(N))
     #14: #a__x(N,0()) -> #a__isNat(N)
     #15: #mark(U11(X1,X2)) -> #a__U11(mark(X1),X2)
     #16: #mark(U11(X1,X2)) -> #mark(X1)
     #17: #mark(and(X1,X2)) -> #a__and(mark(X1),X2)
     #18: #mark(and(X1,X2)) -> #mark(X1)
     #19: #a__isNat(plus(V1,V2)) -> #a__and(a__isNat(V1),isNat(V2))
     #20: #a__isNat(plus(V1,V2)) -> #a__isNat(V1)
     #21: #a__plus(N,0()) -> #a__U11(a__isNat(N),N)
     #22: #a__plus(N,0()) -> #a__isNat(N)
     #23: #a__and(tt(),X) -> #mark(X)
     #24: #mark(U31(X)) -> #a__U31(mark(X))
     #25: #mark(U31(X)) -> #mark(X)
     #26: #mark(x(X1,X2)) -> #a__x(mark(X1),mark(X2))
     #27: #mark(x(X1,X2)) -> #mark(X1)
     #28: #mark(x(X1,X2)) -> #mark(X2)
     #29: #mark(isNat(X)) -> #a__isNat(X)
     #30: #mark(plus(X1,X2)) -> #a__plus(mark(X1),mark(X2))
     #31: #mark(plus(X1,X2)) -> #mark(X1)
     #32: #mark(plus(X1,X2)) -> #mark(X2)
     #33: #a__U11(tt(),N) -> #mark(N)
     #34: #a__isNat(s(V1)) -> #a__isNat(V1)
     #35: #mark(U21(X1,X2,X3)) -> #a__U21(mark(X1),X2,X3)
     #36: #mark(U21(X1,X2,X3)) -> #mark(X1)
     #37: #a__U41(tt(),M,N) -> #a__plus(a__x(mark(N),mark(M)),mark(N))
     #38: #a__U41(tt(),M,N) -> #a__x(mark(N),mark(M))
     #39: #a__U41(tt(),M,N) -> #mark(N)
     #40: #a__U41(tt(),M,N) -> #mark(M)
     #41: #a__U41(tt(),M,N) -> #mark(N)
     #42: #mark(U41(X1,X2,X3)) -> #a__U41(mark(X1),X2,X3)
     #43: #mark(U41(X1,X2,X3)) -> #mark(X1)
Number of SCCs: 1, DPs: 41
  SCC { #1..12 #14..23 #25..43 }
POLO(Sum)... POLO(max)... succeeded.
      a__plus	w: max(x1, x2 + 3)
      U21	w: max(x1 + 1, x2 + 3, x3)
      U11	w: max(x1, x2)
      s 	w: x1
      #a__U31	w: 0
      #a__isNat	w: 2
      and	w: max(x1, x2)
      #a__x	w: max(x1 + 20591, x2 + 5)
      #a__U11	w: max(x2 + 2)
      a__U31	w: x1 + 10531
      a__x	w: max(x1 + 20589, x2 + 3)
      a__U41	w: max(x1 + 20588, x2 + 3, x3 + 20589)
      x 	w: max(x1 + 20589, x2 + 3)
      #a__U21	w: max(x2 + 4, x3 + 2)
      #a__plus	w: max(x1 + 2, x2 + 4)
      #mark	w: x1 + 2
      0 	w: 10527
      #a__and	w: max(x1 + 1, x2 + 2)
      a__U21	w: max(x1 + 1, x2 + 3, x3)
      mark	w: x1
      a__U11	w: max(x1, x2)
      isNat	w: 0
      plus	w: max(x1, x2 + 3)
      U31	w: x1 + 10531
      #a__U41	w: max(x1 + 1, x2 + 5, x3 + 20591)
      tt	w: 0
      a__isNat	w: 0
      a__and	w: max(x1, x2)
      U41	w: max(x1 + 20588, x2 + 3, x3 + 20589)
    USABLE RULES: { 1..32 }
    Removed DPs: #3 #5 #6 #10 #11 #14 #22 #25 #27 #28 #32 #36 #39..41 #43
Number of SCCs: 1, DPs: 25
  SCC { #1 #2 #4 #7..9 #12 #15..21 #23 #26 #29..31 #33..35 #37 #38 #42 }
POLO(Sum)... POLO(max)... succeeded.
      a__plus	w: max(x1, x2 + 10622)
      U21	w: max(x2 + 10622, x3)
      U11	w: max(x1, x2)
      s 	w: x1
      #a__U31	w: 0
      #a__isNat	w: x1 + 1
      and	w: max(x1, x2 + 3825)
      #a__x	w: max(x1 + 11600, x2 + 11599)
      #a__U11	w: max(x1 + 452, x2 + 978)
      a__U31	w: 10474
      a__x	w: max(x1 + 10622, x2 + 10621)
      a__U41	w: max(x1 + 1, x2 + 10621, x3 + 10622)
      x 	w: max(x1 + 10622, x2 + 10621)
      #a__U21	w: max(x3 + 978)
      #a__plus	w: max(x1 + 978)
      #mark	w: x1 + 978
      0 	w: 0
      #a__and	w: max(x2 + 979)
      a__U21	w: max(x2 + 10622, x3)
      mark	w: x1
      a__U11	w: max(x1, x2)
      isNat	w: x1
      plus	w: max(x1, x2 + 10622)
      U31	w: 10474
      #a__U41	w: max(x2 + 11599, x3 + 11600)
      tt	w: 0
      a__isNat	w: x1
      a__and	w: max(x1, x2 + 3825)
      U41	w: max(x1 + 1, x2 + 10621, x3 + 10622)
    USABLE RULES: { 1..32 }
    Removed DPs: #7 #8 #17 #19 #23 #29
Number of SCCs: 2, DPs: 19
  SCC { #20 #34 }
POLO(Sum)... succeeded.
      a__plus	w: 56525
      U21	w: 56527
      U11	w: 56527
      s 	w: x1 + 2
      #a__U31	w: 0
      #a__isNat	w: x1 + 2
      and	w: x1 + 1
      #a__x	w: 0
      #a__U11	w: 2
      a__U31	w: x1 + 1
      a__x	w: x1 + 1
      a__U41	w: x1 + x3 + 1
      x 	w: x2 + 2
      #a__U21	w: 2
      #a__plus	w: 2
      #mark	w: 2
      0 	w: 56525
      #a__and	w: 2
      a__U21	w: 56526
      mark	w: 1
      a__U11	w: 56526
      isNat	w: x1 + 24849
      plus	w: x1 + 56526
      U31	w: 2
      #a__U41	w: 0
      tt	w: 56523
      a__isNat	w: 24848
      a__and	w: x2
      U41	w: 2
    USABLE RULES: { }
    Removed DPs: #20 #34
Number of SCCs: 1, DPs: 17
  SCC { #1 #2 #4 #9 #12 #15 #16 #18 #21 #26 #30 #31 #33 #35 #37 #38 #42 }
POLO(Sum)... POLO(max)... succeeded.
      a__plus	w: max(x1, x2)
      U21	w: max(x2, x3)
      U11	w: max(x1 + 1, x2)
      s 	w: x1
      #a__U31	w: 0
      #a__isNat	w: 1
      and	w: max(x1, x2)
      #a__x	w: max(x1, x2 + 29180)
      #a__U11	w: max(x1, x2)
      a__U31	w: x1 + 5744
      a__x	w: max(x1, x2 + 29180)
      a__U41	w: max(x1 + 29178, x2 + 29180, x3)
      x 	w: max(x1, x2 + 29180)
      #a__U21	w: max(x2, x3)
      #a__plus	w: max(x1, x2)
      #mark	w: x1
      0 	w: 2
      #a__and	w: 0
      a__U21	w: max(x2, x3)
      mark	w: x1
      a__U11	w: max(x1 + 1, x2)
      isNat	w: 1
      plus	w: max(x1, x2)
      U31	w: x1 + 5744
      #a__U41	w: max(x1 + 29178, x2 + 29180, x3)
      tt	w: 1
      a__isNat	w: 1
      a__and	w: max(x1, x2)
      U41	w: max(x1 + 29178, x2 + 29180, x3)
    USABLE RULES: { 1..32 }
    Removed DPs: #16
Number of SCCs: 1, DPs: 16
  SCC { #1 #2 #4 #9 #12 #15 #18 #21 #26 #30 #31 #33 #35 #37 #38 #42 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      a__plus	s: [1,2]	p: 4
      U21	s: [3,2,1]	p: 4
      U11	s: [1,2]	p: 2
      s 	s: [1]	p: 0
      #a__U31	s: []	p: 0
      #a__isNat	s: []	p: 0
      and	s: [2,1]	p: 1
      #a__x	s: [2,1]	p: 5
      #a__U11	s: 2
      a__U31	s: []	p: 6
      a__x	s: [2,1]	p: 5
      a__U41	s: [2,3,1]	p: 5
      x 	s: [2,1]	p: 5
      #a__U21	s: [3]	p: 2
      #a__plus	s: [1]	p: 2
      #mark	s: 1
      0 	s: []	p: 6
      #a__and	s: 1
      a__U21	s: [3,2,1]	p: 4
      mark	s: 1
      a__U11	s: [1,2]	p: 2
      isNat	s: [1]	p: 1
      plus	s: [1,2]	p: 4
      U31	s: []	p: 6
      #a__U41	s: [2,3,1]	p: 5
      tt	s: []	p: 6
      a__isNat	s: [1]	p: 1
      a__and	s: [2,1]	p: 1
      U41	s: [2,3,1]	p: 5
    USABLE RULES: { 1..32 }
    Removed DPs: #2 #4 #12 #15 #18 #21 #30 #31 #35 #37 #38
Number of SCCs: 1, DPs: 2
  SCC { #1 #9 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      a__plus	s: [1,2]	p: 4
      U21	s: [3,2,1]	p: 4
      U11	s: [1,2]	p: 2
      s 	s: [1]	p: 0
      #a__U31	s: []	p: 0
      #a__isNat	s: []	p: 0
      and	s: [2,1]	p: 3
      #a__x	s: [2,1]	p: 5
      #a__U11	s: 2
      a__U31	s: []	p: 7
      a__x	s: [2,1]	p: 5
      a__U41	s: [2,3,1]	p: 5
      x 	s: [2,1]	p: 5
      #a__U21	s: 2
      #a__plus	s: 2
      #mark	s: 1
      0 	s: []	p: 7
      #a__and	s: 1
      a__U21	s: [3,2,1]	p: 4
      mark	s: 1
      a__U11	s: [1,2]	p: 2
      isNat	s: [1]	p: 3
      plus	s: [1,2]	p: 4
      U31	s: []	p: 7
      #a__U41	s: [2,3,1]	p: 5
      tt	s: []	p: 7
      a__isNat	s: [1]	p: 3
      a__and	s: [2,1]	p: 3
      U41	s: [2,3,1]	p: 5
    USABLE RULES: { 1..32 }
    Removed DPs: #9
Number of SCCs: 0, DPs: 0