YES
Input TRS:
      1: 0(\#()) -> \#()
      2: +(x,\#()) -> x
      3: +(\#(),x) -> x
      4: +(0(x),0(y)) -> 0(+(x,y))
      5: +(0(x),1(y)) -> 1(+(x,y))
      6: +(1(x),0(y)) -> 1(+(x,y))
      7: +(1(x),1(y)) -> 0(+(+(x,y),1(\#())))
      8: +(+(x,y),z) -> +(x,+(y,z))
      9: *(\#(),x) -> \#()
      10: *(0(x),y) -> 0(*(x,y))
      11: *(1(x),y) -> +(0(*(x,y)),y)
      12: *(*(x,y),z) -> *(x,*(y,z))
      13: *(x,+(y,z)) -> +(*(x,y),*(x,z))
      14: app(nil(),l) -> l
      15: app(cons(x,l1),l2) -> cons(x,app(l1,l2))
      16: sum(nil()) -> 0(\#())
      17: sum(cons(x,l)) -> +(x,sum(l))
      18: sum(app(l1,l2)) -> +(sum(l1),sum(l2))
      19: prod(nil()) -> 1(\#())
      20: prod(cons(x,l)) -> *(x,prod(l))
      21: prod(app(l1,l2)) -> *(prod(l1),prod(l2))
Number of strict rules: 21
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #+(1(x),0(y)) -> #+(x,y)
     #2: #*(x,+(y,z)) -> #+(*(x,y),*(x,z))
     #3: #*(x,+(y,z)) -> #*(x,y)
     #4: #*(x,+(y,z)) -> #*(x,z)
     #5: #*(1(x),y) -> #+(0(*(x,y)),y)
     #6: #*(1(x),y) -> #0(*(x,y))
     #7: #*(1(x),y) -> #*(x,y)
     #8: #*(*(x,y),z) -> #*(x,*(y,z))
     #9: #*(*(x,y),z) -> #*(y,z)
     #10: #prod(cons(x,l)) -> #*(x,prod(l))
     #11: #prod(cons(x,l)) -> #prod(l)
     #12: #+(1(x),1(y)) -> #0(+(+(x,y),1(\#())))
     #13: #+(1(x),1(y)) -> #+(+(x,y),1(\#()))
     #14: #+(1(x),1(y)) -> #+(x,y)
     #15: #*(0(x),y) -> #0(*(x,y))
     #16: #*(0(x),y) -> #*(x,y)
     #17: #+(0(x),1(y)) -> #+(x,y)
     #18: #sum(cons(x,l)) -> #+(x,sum(l))
     #19: #sum(cons(x,l)) -> #sum(l)
     #20: #prod(app(l1,l2)) -> #*(prod(l1),prod(l2))
     #21: #prod(app(l1,l2)) -> #prod(l1)
     #22: #prod(app(l1,l2)) -> #prod(l2)
     #23: #sum(nil()) -> #0(\#())
     #24: #+(+(x,y),z) -> #+(x,+(y,z))
     #25: #+(+(x,y),z) -> #+(y,z)
     #26: #app(cons(x,l1),l2) -> #app(l1,l2)
     #27: #+(0(x),0(y)) -> #0(+(x,y))
     #28: #+(0(x),0(y)) -> #+(x,y)
     #29: #sum(app(l1,l2)) -> #+(sum(l1),sum(l2))
     #30: #sum(app(l1,l2)) -> #sum(l1)
     #31: #sum(app(l1,l2)) -> #sum(l2)
Number of SCCs: 5, DPs: 20
  SCC { #26 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: 0
      #* 	w: 0
      \#	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      #app	w: x1
      cons	w: x2 + 1
      + 	w: 0
      #sum	w: 0
      #+ 	w: 0
      * 	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #26
Number of SCCs: 4, DPs: 19
  SCC { #19 #30 #31 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: 0
      #* 	w: 0
      \#	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      #app	w: 0
      cons	w: x2 + 1
      + 	w: 0
      #sum	w: x1
      #+ 	w: 0
      * 	w: 0
      app	w: x1 + x2 + 1
    USABLE RULES: { }
    Removed DPs: #19 #30 #31
Number of SCCs: 3, DPs: 16
  SCC { #11 #21 #22 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: x1
      #* 	w: 0
      \#	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      #app	w: 0
      cons	w: x2 + 1
      + 	w: 0
      #sum	w: 0
      #+ 	w: 0
      * 	w: 0
      app	w: x1 + x2 + 1
    USABLE RULES: { }
    Removed DPs: #11 #21 #22
Number of SCCs: 2, DPs: 13
  SCC { #3 #4 #7..9 #16 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: x1 + 2
      prod	w: 0
      #prod	w: 0
      #* 	w: x1
      \#	w: 1
      sum	w: 0
      0 	w: x1 + 1
      nil	w: 0
      #app	w: 0
      cons	w: 1
      + 	w: x2 + 4
      #sum	w: 0
      #+ 	w: 0
      * 	w: x1 + x2 + 1
      app	w: 1
    USABLE RULES: { }
    Removed DPs: #7..9 #16
Number of SCCs: 2, DPs: 9
  SCC { #3 #4 }
POLO(Sum)... POLO(max)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: 0
      #* 	w: max(x2 + 1)
      \#	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      #app	w: 0
      cons	w: 0
      + 	w: max(x1 + 1, x2)
      #sum	w: 0
      #+ 	w: 0
      * 	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #3
Number of SCCs: 2, DPs: 8
  SCC { #4 }
POLO(Sum)... POLO(max)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: 0
      #* 	w: max(x2 + 11293)
      \#	w: 0
      sum	w: 0
      0 	w: 0
      nil	w: 0
      #app	w: 0
      cons	w: 0
      + 	w: max(x2 + 21239)
      #sum	w: 0
      #+ 	w: 0
      * 	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #4
Number of SCCs: 1, DPs: 7
  SCC { #1 #13 #14 #17 #24 #25 #28 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: x1 + 20540
      prod	w: 0
      #prod	w: 0
      #* 	w: 0
      \#	w: 1
      sum	w: 0
      0 	w: x1 + 1
      nil	w: 0
      #app	w: 0
      cons	w: 1
      + 	w: x1 + x2 + 20538
      #sum	w: 0
      #+ 	w: x1 + x2
      * 	w: x1 + 24867
      app	w: 1
    USABLE RULES: { 1..8 }
    Removed DPs: #1 #13 #14 #17 #25 #28
Number of SCCs: 1, DPs: 1
  SCC { #24 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: x1 + 53549
      prod	w: 0
      #prod	w: 0
      #* 	w: 0
      \#	w: 1
      sum	w: 0
      0 	w: x1 + 53547
      nil	w: 0
      #app	w: 0
      cons	w: 1
      + 	w: x1 + x2 + 1
      #sum	w: 0
      #+ 	w: x1
      * 	w: x1 + 1
      app	w: 1
    USABLE RULES: { 1..8 }
    Removed DPs: #24
Number of SCCs: 0, DPs: 0