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