YES

TRS:

  a__U11(tt(),M,N) -> a__U12(tt(),M,N)
  a__U12(tt(),M,N) -> s(a__plus(mark(N),mark(M)))
  a__plus(N,0()) -> mark(N)
  a__plus(N,s(M)) -> a__U11(tt(),M,N)
  mark(U11(X1,X2,X3)) -> a__U11(mark(X1),X2,X3)
  mark(U12(X1,X2,X3)) -> a__U12(mark(X1),X2,X3)
  mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
  mark(tt()) -> tt()
  mark(s(X)) -> s(mark(X))
  mark(0()) -> 0()
  a__U11(X1,X2,X3) -> U11(X1,X2,X3)
  a__U12(X1,X2,X3) -> U12(X1,X2,X3)
  a__plus(X1,X2) -> plus(X1,X2)

linear polynomial interpretations on N:

  a__U11_A(x1,x2,x3) = x1 + x2 + x3 + 4
  a__U11#_A(x1,x2,x3) = x2 + x3 + 5
  tt_A = 1
  tt#_A = 0
  a__U12_A(x1,x2,x3) = x1 + x2 + x3 + 4
  a__U12#_A(x1,x2,x3) = x2 + x3 + 4
  s_A(x1) = x1 + 3
  s#_A(x1) = 1
  a__plus_A(x1,x2) = x1 + x2 + 2
  a__plus#_A(x1,x2) = x1 + x2 + 3
  mark_A(x1) = x1
  mark#_A(x1) = x1 + 2
  0_A = 1
  0#_A = 0
  U11_A(x1,x2,x3) = x1 + x2 + x3 + 4
  U11#_A(x1,x2,x3) = 1
  U12_A(x1,x2,x3) = x1 + x2 + x3 + 4
  U12#_A(x1,x2,x3) = 3
  plus_A(x1,x2) = x1 + x2 + 2
  plus#_A(x1,x2) = x1 + 1

precedence:

  U12 > mark > a__U11 = 0 > a__U12 = U11 > s = a__plus > tt = plus