MAYBE
Input TRS:
      1: a__p(0()) -> 0()
      2: a__p(s(X)) -> mark(X)
      3: a__leq(0(),Y) -> true()
      4: a__leq(s(X),0()) -> false()
      5: a__leq(s(X),s(Y)) -> a__leq(mark(X),mark(Y))
      6: a__if(true(),X,Y) -> mark(X)
      7: a__if(false(),X,Y) -> mark(Y)
      8: a__diff(X,Y) -> a__if(a__leq(mark(X),mark(Y)),0(),s(diff(p(X),Y)))
      9: mark(p(X)) -> a__p(mark(X))
      10: mark(leq(X1,X2)) -> a__leq(mark(X1),mark(X2))
      11: mark(if(X1,X2,X3)) -> a__if(mark(X1),X2,X3)
      12: mark(diff(X1,X2)) -> a__diff(mark(X1),mark(X2))
      13: mark(0()) -> 0()
      14: mark(s(X)) -> s(mark(X))
      15: mark(true()) -> true()
      16: mark(false()) -> false()
      17: a__p(X) -> p(X)
      18: a__leq(X1,X2) -> leq(X1,X2)
      19: a__if(X1,X2,X3) -> if(X1,X2,X3)
      20: a__diff(X1,X2) -> diff(X1,X2)
Number of strict rules: 20
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #a__p(s(X)) -> #mark(X)
     #2: #a__if(true(),X,Y) -> #mark(X)
     #3: #mark(p(X)) -> #a__p(mark(X))
     #4: #mark(p(X)) -> #mark(X)
     #5: #mark(if(X1,X2,X3)) -> #a__if(mark(X1),X2,X3)
     #6: #mark(if(X1,X2,X3)) -> #mark(X1)
     #7: #mark(diff(X1,X2)) -> #a__diff(mark(X1),mark(X2))
     #8: #mark(diff(X1,X2)) -> #mark(X1)
     #9: #mark(diff(X1,X2)) -> #mark(X2)
     #10: #mark(s(X)) -> #mark(X)
     #11: #a__if(false(),X,Y) -> #mark(Y)
     #12: #mark(leq(X1,X2)) -> #a__leq(mark(X1),mark(X2))
     #13: #mark(leq(X1,X2)) -> #mark(X1)
     #14: #mark(leq(X1,X2)) -> #mark(X2)
     #15: #a__leq(s(X),s(Y)) -> #a__leq(mark(X),mark(Y))
     #16: #a__leq(s(X),s(Y)) -> #mark(X)
     #17: #a__leq(s(X),s(Y)) -> #mark(Y)
     #18: #a__diff(X,Y) -> #a__if(a__leq(mark(X),mark(Y)),0(),s(diff(p(X),Y)))
     #19: #a__diff(X,Y) -> #a__leq(mark(X),mark(Y))
     #20: #a__diff(X,Y) -> #mark(X)
     #21: #a__diff(X,Y) -> #mark(Y)
Number of SCCs: 1, DPs: 21
  SCC { #1..21 }
POLO(Sum)... POLO(max)... succeeded.
      #a__diff	w: max(x1 + 38736, x2 + 58756)
      diff	w: max(x1, x2 + 20020)
      s 	w: x1
      false	w: 593
      a__p	w: x1
      leq	w: max(x1, x2 + 592)
      a__leq	w: max(x1, x2 + 592)
      true	w: 592
      p 	w: x1
      #mark	w: x1 + 38736
      0 	w: 592
      if	w: max(x1, x2 + 19428, x3)
      a__diff	w: max(x1, x2 + 20020)
      mark	w: x1
      #a__p	w: x1 + 38736
      #a__leq	w: max(x1 + 38736, x2 + 38737)
      #a__if	w: max(x1 + 38145, x2 + 58164, x3 + 38736)
      a__if	w: max(x1, x2 + 19428, x3)
    USABLE RULES: { 1..20 }
    Removed DPs: #2 #9 #14 #17 #21
Number of SCCs: 1, DPs: 16
  SCC { #1 #3..8 #10..13 #15 #16 #18..20 }
POLO(Sum)... POLO(max)... succeeded.
      #a__diff	w: max(x1 + 4, x2 + 5)
      diff	w: max(x1 + 1, x2 + 2)
      s 	w: x1
      false	w: 3
      a__p	w: x1
      leq	w: max(x1, x2 + 2)
      a__leq	w: max(x1, x2 + 2)
      true	w: 1
      p 	w: x1
      #mark	w: x1 + 3
      0 	w: 1
      if	w: max(x1, x2 + 1, x3)
      a__diff	w: max(x1 + 1, x2 + 2)
      mark	w: x1
      #a__p	w: x1 + 3
      #a__leq	w: max(x1 + 3, x2 + 2)
      #a__if	w: max(x1 + 1, x3 + 3)
      a__if	w: max(x1, x2 + 1, x3)
    USABLE RULES: { 1..20 }
    Removed DPs: #8 #19 #20
Number of SCCs: 1, DPs: 13
  SCC { #1 #3..7 #10..13 #15 #16 #18 }
POLO(Sum)... POLO(max)... succeeded.
      #a__diff	w: max(x1 + 15243, x2 + 15244)
      diff	w: max(x1 + 2, x2 + 3)
      s 	w: x1
      false	w: 4
      a__p	w: x1
      leq	w: max(x1 + 2, x2 + 3)
      a__leq	w: max(x1 + 2, x2 + 3)
      true	w: 1
      p 	w: x1
      #mark	w: x1 + 15241
      0 	w: 2
      if	w: max(x1, x2 + 1, x3)
      a__diff	w: max(x1 + 2, x2 + 3)
      mark	w: x1
      #a__p	w: x1 + 15241
      #a__leq	w: max(x1 + 15242, x2 + 15240)
      #a__if	w: max(x1 + 15239, x3 + 15241)
      a__if	w: max(x1, x2 + 1, x3)
    USABLE RULES: { 1..20 }
    Removed DPs: #12 #13 #16
Number of SCCs: 2, DPs: 10
  SCC { #15 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.