YES

TRS:

  a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z)))
  a____(X,nil()) -> mark(X)
  a____(nil(),X) -> mark(X)
  a__U11(tt()) -> a__U12(tt())
  a__U12(tt()) -> tt()
  a__isNePal(__(I,__(P,I))) -> a__U11(tt())
  mark(__(X1,X2)) -> a____(mark(X1),mark(X2))
  mark(U11(X)) -> a__U11(mark(X))
  mark(U12(X)) -> a__U12(mark(X))
  mark(isNePal(X)) -> a__isNePal(mark(X))
  mark(nil()) -> nil()
  mark(tt()) -> tt()
  a____(X1,X2) -> __(X1,X2)
  a__U11(X) -> U11(X)
  a__U12(X) -> U12(X)
  a__isNePal(X) -> isNePal(X)

linear polynomial interpretations on N:

  a_____A(x1,x2) = x1 + x2 + 2
  a____#_A(x1,x2) = x1 + x2 + 4
  ___A(x1,x2) = x1 + x2 + 2
  __#_A(x1,x2) = x1 + x2 + 3
  mark_A(x1) = x1
  mark#_A(x1) = x1 + 3
  nil_A = 1
  nil#_A = 0
  a__U11_A(x1) = x1 + 1
  a__U11#_A(x1) = 2
  tt_A = 1
  tt#_A = 0
  a__U12_A(x1) = x1 + 1
  a__U12#_A(x1) = 1
  a__isNePal_A(x1) = x1 + 3
  a__isNePal#_A(x1) = 5
  U11_A(x1) = x1 + 1
  U11#_A(x1) = 1
  U12_A(x1) = x1 + 1
  U12#_A(x1) = 0
  isNePal_A(x1) = x1 + 3
  isNePal#_A(x1) = 4

precedence:

  U12 = isNePal > __ = mark > a____ = nil = a__U12 = a__isNePal > a__U11 > tt = U11