YES
Input TRS:
AC symbols: plus
      1: app(nil(),k) -> k
      2: app(l,nil()) -> l
      3: app(cons(x,l),k) -> cons(x,app(l,k))
      4: sum(cons(x,nil())) -> cons(x,nil())
      5: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l))
      6: sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k)))))
      7: sum(cons(0(),cons(plus(x,y),l))) -> pred(sum(cons(s(x),cons(y,l))))
      8: plus(0(),y) -> y
      9: plus(s(x),y) -> s(plus(x,y))
      10: pred(cons(s(x),nil())) -> cons(x,nil())
Number of strict rules: 10
Direct POLO(bPol) ... removes: 8 1 3 5 10 7 2
      s 	w: x1 + 1
      pred	w: x1
      sum	w: x1
      0 	w: 14681
      nil	w: 26286
      plus	w: x1 + x2 + 1
      cons	w: 2 * x1 + x2 + 3000
      app	w: 2 * x1 + x2 + 2
Number of strict rules: 3
Direct POLO(bPol) ... failed.
Uncurrying sum
AC symbols: plus
      4: sum^1_cons(x,nil()) -> cons(x,nil())
      6: sum^1_app(l,cons(x,cons(y,k))) -> sum^1_app(l,sum^1_cons(x,cons(y,k)))
      9: plus(s(x),y) -> s(plus(x,y))
      11: sum(cons(_1,_2)) ->= sum^1_cons(_1,_2)
      12: sum(app(_1,_2)) ->= sum^1_app(_1,_2)
Number of strict rules: 3
Direct POLO(bPol) ... removes: 4 12 11 6
      sum^1_app	w: x1 + 2 * x2
      s 	w: x1
      sum^1_cons	w: x1 + x2 + 8370
      pred	w: x1
      sum	w: 2 * x1 + 2
      0 	w: 0
      nil	w: 1
      plus	w: x1 + x2
      cons	w: x1 + 2 * x2 + 8368
      app	w: x1 + x2 + 1
Number of strict rules: 1
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #plus(x,plus(y,z)) ->= #plus(plus(x,y),z)
     #2: #plus(x,plus(y,z)) ->= #plus(x,y)
     #3: #plus(s(x),y) -> #plus(x,y)
Number of SCCs: 1, DPs: 3
  SCC { #1..3 }
POLO(Sum)... succeeded.
      sum^1_app	w: 0
      s 	w: x1 + 1
      sum^1_cons	w: 0
      #plus	w: x1 + x2
      pred	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      plus	w: x1 + x2 + 39
      cons	w: 0
      app	w: 0
    USABLE RULES: { 9 13 }
    Removed DPs: #2 #3
Number of SCCs: 1, DPs: 1
  SCC { #1 }
only weak rules.
Number of SCCs: 0, DPs: 0
Next Dependency Pairs:
     #4: #plus(x,plus(y,z)) ->= #plus(plus(x,y),z)
     #5: #plus(x,plus(y,z)) ->= #plus(x,y)
     #6: #plus(plus(s(x),y),_1) -> #plus(s(plus(x,y)),_1)
Number of SCCs: 1, DPs: 3
  SCC { #4..6 }
POLO(Sum)... succeeded.
      sum^1_app	w: 0
      s 	w: 23676
      sum^1_cons	w: 0
      #plus	w: x1 + x2
      pred	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      plus	w: x1 + x2 + 1
      cons	w: 0
      app	w: 0
    USABLE RULES: { 9 13 }
    Removed DPs: #5 #6
Number of SCCs: 1, DPs: 1
  SCC { #4 }
only weak rules.
Number of SCCs: 0, DPs: 0