YES
Input TRS:
      1: a__and(tt(),X) -> mark(X)
      2: a__plus(N,0()) -> mark(N)
      3: a__plus(N,s(M)) -> s(a__plus(mark(N),mark(M)))
      4: mark(and(X1,X2)) -> a__and(mark(X1),X2)
      5: mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
      6: mark(tt()) -> tt()
      7: mark(0()) -> 0()
      8: mark(s(X)) -> s(mark(X))
      9: a__and(X1,X2) -> and(X1,X2)
      10: a__plus(X1,X2) -> plus(X1,X2)
Number of strict rules: 10
Direct POLO(bPol) ... removes: 1 2
      a__plus	w: x1 + x2 + 10451
      s 	w: x1 + 1
      and	w: x1 + x2 + 1
      0 	w: 30613
      mark	w: x1
      plus	w: x1 + x2 + 10451
      tt	w: 1
      a__and	w: x1 + x2 + 1
Number of strict rules: 8
Direct POLO(bPol) ... removes: 3
      a__plus	w: 2 * x1 + 2 * x2 + 18458
      s 	w: x1 + 25907
      and	w: x1 + 2 * x2 + 1
      0 	w: 1324
      mark	w: x1
      plus	w: 2 * x1 + 2 * x2 + 18458
      tt	w: 1
      a__and	w: x1 + 2 * x2 + 1
Number of strict rules: 7
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #mark(plus(X1,X2)) -> #a__plus(mark(X1),mark(X2))
     #2: #mark(plus(X1,X2)) -> #mark(X1)
     #3: #mark(plus(X1,X2)) -> #mark(X2)
     #4: #mark(s(X)) -> #mark(X)
     #5: #mark(and(X1,X2)) -> #a__and(mark(X1),X2)
     #6: #mark(and(X1,X2)) -> #mark(X1)
Number of SCCs: 1, DPs: 4
  SCC { #2..4 #6 }
POLO(Sum)... succeeded.
      a__plus	w: 0
      s 	w: x1 + 1
      and	w: x1 + 1
      #a__plus	w: 0
      #mark	w: x1
      0 	w: 0
      #a__and	w: 0
      mark	w: 0
      plus	w: x1 + x2 + 1
      tt	w: 0
      a__and	w: 0
    USABLE RULES: { }
    Removed DPs: #2..4 #6
Number of SCCs: 0, DPs: 0