YES
Input TRS:
      1: a__U11(tt(),M,N) -> a__U12(tt(),M,N)
      2: a__U12(tt(),M,N) -> s(a__plus(mark(N),mark(M)))
      3: a__U21(tt(),M,N) -> a__U22(tt(),M,N)
      4: a__U22(tt(),M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
      5: a__plus(N,0()) -> mark(N)
      6: a__plus(N,s(M)) -> a__U11(tt(),M,N)
      7: a__x(N,0()) -> 0()
      8: a__x(N,s(M)) -> a__U21(tt(),M,N)
      9: mark(U11(X1,X2,X3)) -> a__U11(mark(X1),X2,X3)
      10: mark(U12(X1,X2,X3)) -> a__U12(mark(X1),X2,X3)
      11: mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
      12: mark(U21(X1,X2,X3)) -> a__U21(mark(X1),X2,X3)
      13: mark(U22(X1,X2,X3)) -> a__U22(mark(X1),X2,X3)
      14: mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
      15: mark(tt()) -> tt()
      16: mark(s(X)) -> s(mark(X))
      17: mark(0()) -> 0()
      18: a__U11(X1,X2,X3) -> U11(X1,X2,X3)
      19: a__U12(X1,X2,X3) -> U12(X1,X2,X3)
      20: a__plus(X1,X2) -> plus(X1,X2)
      21: a__U21(X1,X2,X3) -> U21(X1,X2,X3)
      22: a__U22(X1,X2,X3) -> U22(X1,X2,X3)
      23: a__x(X1,X2) -> x(X1,X2)
Number of strict rules: 23
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #a__U12(tt(),M,N) -> #a__plus(mark(N),mark(M))
     #2: #a__U12(tt(),M,N) -> #mark(N)
     #3: #a__U12(tt(),M,N) -> #mark(M)
     #4: #a__plus(N,s(M)) -> #a__U11(tt(),M,N)
     #5: #mark(U22(X1,X2,X3)) -> #a__U22(mark(X1),X2,X3)
     #6: #mark(U22(X1,X2,X3)) -> #mark(X1)
     #7: #mark(U11(X1,X2,X3)) -> #a__U11(mark(X1),X2,X3)
     #8: #mark(U11(X1,X2,X3)) -> #mark(X1)
     #9: #mark(plus(X1,X2)) -> #a__plus(mark(X1),mark(X2))
     #10: #mark(plus(X1,X2)) -> #mark(X1)
     #11: #mark(plus(X1,X2)) -> #mark(X2)
     #12: #mark(U21(X1,X2,X3)) -> #a__U21(mark(X1),X2,X3)
     #13: #mark(U21(X1,X2,X3)) -> #mark(X1)
     #14: #mark(x(X1,X2)) -> #a__x(mark(X1),mark(X2))
     #15: #mark(x(X1,X2)) -> #mark(X1)
     #16: #mark(x(X1,X2)) -> #mark(X2)
     #17: #mark(U12(X1,X2,X3)) -> #a__U12(mark(X1),X2,X3)
     #18: #mark(U12(X1,X2,X3)) -> #mark(X1)
     #19: #a__plus(N,0()) -> #mark(N)
     #20: #mark(s(X)) -> #mark(X)
     #21: #a__U21(tt(),M,N) -> #a__U22(tt(),M,N)
     #22: #a__U11(tt(),M,N) -> #a__U12(tt(),M,N)
     #23: #a__x(N,s(M)) -> #a__U21(tt(),M,N)
     #24: #a__U22(tt(),M,N) -> #a__plus(a__x(mark(N),mark(M)),mark(N))
     #25: #a__U22(tt(),M,N) -> #a__x(mark(N),mark(M))
     #26: #a__U22(tt(),M,N) -> #mark(N)
     #27: #a__U22(tt(),M,N) -> #mark(M)
     #28: #a__U22(tt(),M,N) -> #mark(N)
Number of SCCs: 1, DPs: 28
  SCC { #1..28 }
POLO(Sum)... POLO(max)... succeeded.
      a__plus	w: max(x1, x2 + 18815)
      U21	w: max(x1 + 13215, x2 + 1, x3 + 18815)
      U11	w: max(x1 + 18814, x2 + 18815, x3)
      s 	w: x1
      #a__x	w: max(x1 + 75553, x2 + 56739)
      a__U22	w: max(x1 + 18814, x2 + 1, x3 + 18815)
      #a__U11	w: max(x1 + 75552, x2 + 75553, x3 + 56738)
      a__x	w: max(x1 + 18815, x2 + 1)
      U12	w: max(x1 + 18814, x2 + 18815, x3)
      x 	w: max(x1 + 18815, x2 + 1)
      #a__U12	w: max(x1 + 75551, x2 + 75553, x3 + 56738)
      #a__U21	w: max(x2 + 56739, x3 + 75553)
      #a__plus	w: max(x1 + 56738, x2 + 75553)
      #mark	w: x1 + 56738
      0 	w: 4684
      a__U21	w: max(x1 + 13215, x2 + 1, x3 + 18815)
      mark	w: x1
      a__U11	w: max(x1 + 18814, x2 + 18815, x3)
      a__U12	w: max(x1 + 18814, x2 + 18815, x3)
      plus	w: max(x1, x2 + 18815)
      #a__U22	w: max(x1 + 31964, x2 + 56739, x3 + 75553)
      tt	w: 1
      U22	w: max(x1 + 18814, x2 + 1, x3 + 18815)
    USABLE RULES: { 1..23 }
    Removed DPs: #3 #6 #8 #11 #13 #15 #16 #18 #26..28
Number of SCCs: 1, DPs: 17
  SCC { #1 #2 #4 #5 #7 #9 #10 #12 #14 #17 #19..25 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      a__plus	s: [1,2]	p: 3
      U21	s: [3,2,1]	p: 4
      U11	s: [3,2,1]	p: 3
      s 	s: [1]	p: 0
      #a__x	s: [1,2]	p: 4
      a__U22	s: [3,2,1]	p: 4
      #a__U11	s: 3
      a__x	s: [1,2]	p: 4
      U12	s: [3,2,1]	p: 3
      x 	s: [1,2]	p: 4
      #a__U12	s: 3
      #a__U21	s: [3,2,1]	p: 4
      #a__plus	s: 1
      #mark	s: 1
      0 	s: []	p: 2
      a__U21	s: [3,2,1]	p: 4
      mark	s: 1
      a__U11	s: [3,2,1]	p: 3
      a__U12	s: [3,2,1]	p: 3
      plus	s: [1,2]	p: 3
      #a__U22	s: [3,2]	p: 4
      tt	s: []	p: 2
      U22	s: [3,2,1]	p: 4
    USABLE RULES: { 1..23 }
    Removed DPs: #5 #7 #9 #10 #17 #20 #21 #23
Number of SCCs: 1, DPs: 3
  SCC { #1 #4 #22 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      a__plus	s: [1,2]	p: 4
      U21	s: [3,2,1]	p: 5
      U11	s: [3,2,1]	p: 4
      s 	s: [1]	p: 3
      #a__x	s: [1,2]	p: 4
      a__U22	s: [3,2,1]	p: 5
      #a__U11	s: 2
      a__x	s: [1,2]	p: 5
      U12	s: [3,2,1]	p: 4
      x 	s: [1,2]	p: 5
      #a__U12	s: 2
      #a__U21	s: [3,2,1]	p: 4
      #a__plus	s: 2
      #mark	s: 1
      0 	s: []	p: 1
      a__U21	s: [3,2,1]	p: 5
      mark	s: 1
      a__U11	s: [3,2,1]	p: 4
      a__U12	s: [3,2,1]	p: 4
      plus	s: [1,2]	p: 4
      #a__U22	s: [3,2]	p: 4
      tt	s: []	p: 2
      U22	s: [3,2,1]	p: 5
    USABLE RULES: { 1..23 }
    Removed DPs: #4
Number of SCCs: 0, DPs: 0