MAYBE
Input TRS:
AC symbols: + U *
      1: 0(\#()) -> \#()
      2: +(\#(),x) -> x
      3: +(0(x),0(y)) -> 0(+(x,y))
      4: +(0(x),1(y)) -> 1(+(x,y))
      5: +(1(x),1(y)) -> 0(+(1(\#()),+(x,y)))
      6: *(\#(),x) -> \#()
      7: *(0(x),y) -> 0(*(x,y))
      8: *(1(x),y) -> +(0(*(x,y)),y)
      9: *(+(y,z),x) -> +(*(x,y),*(x,z))
      10: U(empty(),b) -> b
      11: sum(empty()) -> 0(\#())
      12: sum(singl(x)) -> x
      13: sum(U(x,y)) -> +(sum(x),sum(y))
      14: prod(empty()) -> 1(\#())
      15: prod(singl(x)) -> x
      16: prod(U(x,y)) -> *(prod(x),prod(y))
Number of strict rules: 16
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #sum(U(x,y)) -> #+(sum(x),sum(y))
     #2: #sum(U(x,y)) -> #sum(x)
     #3: #sum(U(x,y)) -> #sum(y)
     #4: #*(+(y,z),x) -> #+(*(x,y),*(x,z))
     #5: #*(+(y,z),x) -> #*(x,y)
     #6: #*(+(y,z),x) -> #*(x,z)
     #7: #sum(empty()) -> #0(\#())
     #8: #*(0(x),y) -> #0(*(x,y))
     #9: #*(0(x),y) -> #*(x,y)
     #10: #+(1(x),1(y)) -> #0(+(1(\#()),+(x,y)))
     #11: #+(1(x),1(y)) -> #+(1(\#()),+(x,y))
     #12: #+(1(x),1(y)) -> #+(x,y)
     #13: #+(x,+(y,z)) ->= #+(+(x,y),z)
     #14: #+(x,+(y,z)) ->= #+(x,y)
     #15: #*(x,*(y,z)) ->= #*(*(x,y),z)
     #16: #*(x,*(y,z)) ->= #*(x,y)
     #17: #prod(U(x,y)) -> #*(prod(x),prod(y))
     #18: #prod(U(x,y)) -> #prod(x)
     #19: #prod(U(x,y)) -> #prod(y)
     #20: #+(0(x),0(y)) -> #0(+(x,y))
     #21: #+(0(x),0(y)) -> #+(x,y)
     #22: #*(1(x),y) -> #+(0(*(x,y)),y)
     #23: #*(1(x),y) -> #0(*(x,y))
     #24: #*(1(x),y) -> #*(x,y)
     #25: #+(0(x),1(y)) -> #+(x,y)
     #26: #U(x,U(y,z)) ->= #U(U(x,y),z)
     #27: #U(x,U(y,z)) ->= #U(x,y)
Number of SCCs: 5, DPs: 18
  SCC { #18 #19 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: x1
      #* 	w: 0
      \#	w: 0
      #U 	w: 0
      sum	w: 0
      0 	w: 0
      singl	w: 0
      empty	w: 0
      + 	w: 0
      #sum	w: 0
      U 	w: x1 + x2 + 1
      #+ 	w: 0
      * 	w: 0
    USABLE RULES: { }
    Removed DPs: #18 #19
Number of SCCs: 4, DPs: 16
  SCC { #2 #3 }
POLO(Sum)... succeeded.
      #0 	w: 0
      1 	w: 0
      prod	w: 0
      #prod	w: 0
      #* 	w: 0
      \#	w: 0
      #U 	w: 0
      sum	w: 0
      0 	w: 0
      singl	w: 0
      empty	w: 0
      + 	w: 0
      #sum	w: x1
      U 	w: x1 + x2 + 1
      #+ 	w: 0
      * 	w: 0
    USABLE RULES: { }
    Removed DPs: #2 #3
Number of SCCs: 3, DPs: 14
  SCC { #26 #27 }
only weak rules.
Number of SCCs: 2, DPs: 12
  SCC { #5 #6 #9 #15 #16 #24 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded.
      #0 	w: 0
      1 	w: max(x1, 0)
      prod	w: max(x1 - 1, 0)
      #prod	w: max(x1 - 1, 0)
      #* 	w: max(x1 + x2 + 1, 0)
      \#	w: 0
      #U 	w: max(x1 + x2 - 1, 0)
      sum	w: max(x1 - 1, 0)
      0 	w: max(x1, 0)
      singl	w: max(x1 - 1, 0)
      empty	w: 0
      + 	w: max(x1, x2, 0)
      #sum	w: max(x1 - 1, 0)
      U 	w: max(x1 + x2 - 1, 0)
      #+ 	w: 0
      * 	w: max(x1 + x2 + 39, 0)
    USABLE RULES: { 1..9 17 19 }
    Removed DPs: #16
Number of SCCs: 2, DPs: 11
  SCC { #5 #6 #9 #15 #24 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.