YES
Input TRS:
AC symbols: + U *
      1: +(0(),x) -> x
      2: +(s(x),s(y)) -> s(s(+(x,y)))
      3: *(0(),x) -> 0()
      4: *(s(x),s(y)) -> s(+(+(x,y),*(x,y)))
      5: U(empty(),b) -> b
      6: sum(empty()) -> 0()
      7: sum(singl(x)) -> x
      8: sum(U(x,y)) -> +(sum(x),sum(y))
      9: prod(empty()) -> s(0())
      10: prod(singl(x)) -> x
      11: prod(U(x,y)) -> *(prod(x),prod(y))
Number of strict rules: 11
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #+(s(x),s(y)) -> #+(x,y)
     #2: #U(x,U(y,z)) ->= #U(U(x,y),z)
     #3: #U(x,U(y,z)) ->= #U(x,y)
     #4: #prod(U(x,y)) -> #*(prod(x),prod(y))
     #5: #prod(U(x,y)) -> #prod(x)
     #6: #prod(U(x,y)) -> #prod(y)
     #7: #+(x,+(y,z)) ->= #+(+(x,y),z)
     #8: #+(x,+(y,z)) ->= #+(x,y)
     #9: #*(x,*(y,z)) ->= #*(*(x,y),z)
     #10: #*(x,*(y,z)) ->= #*(x,y)
     #11: #sum(U(x,y)) -> #+(sum(x),sum(y))
     #12: #sum(U(x,y)) -> #sum(x)
     #13: #sum(U(x,y)) -> #sum(y)
     #14: #*(s(x),s(y)) -> #+(+(x,y),*(x,y))
     #15: #*(s(x),s(y)) -> #+(x,y)
     #16: #*(s(x),s(y)) -> #*(x,y)
Number of SCCs: 5, DPs: 12
  SCC { #12 #13 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: 0
      #prod	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: #12 #13
Number of SCCs: 4, DPs: 10
  SCC { #5 #6 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: 0
      #prod	w: x1
      #* 	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: #5 #6
Number of SCCs: 3, DPs: 8
  SCC { #2 #3 }
only weak rules.
Number of SCCs: 2, DPs: 6
  SCC { #9 #10 #16 }
POLO(Sum)... POLO(max)... QLPOS... succeeded.
      prod	s: []	p: 0
      s 	s: [1]	p: 0
      #prod	s: 1
      #* 	s: {1,2}	p: 2
      #U 	s: {}	p: 0
      sum	s: []	p: 0
      0 	s: []	p: 0
      singl	s: []	p: 0
      empty	s: []	p: 0
      + 	s: {1,2}	p: 1
      #sum	s: []	p: 0
      U 	s: {}	p: 0
      #+ 	s: {}	p: 1
      * 	s: {1,2}	p: 2
    USABLE RULES: { 1..4 12 14 }
    Removed DPs: #10 #16
Number of SCCs: 2, DPs: 4
  SCC { #9 }
only weak rules.
Number of SCCs: 1, DPs: 3
  SCC { #1 #7 #8 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: x1 + 1
      #prod	w: 0
      #* 	w: 0
      #U 	w: 0
      sum	w: 0
      0 	w: 1
      singl	w: 0
      empty	w: 0
      + 	w: x1 + x2 + 7720
      #sum	w: 0
      U 	w: 1
      #+ 	w: x1 + x2
      * 	w: x1 + x2
    USABLE RULES: { 1 2 12 }
    Removed DPs: #1 #8
Number of SCCs: 1, DPs: 1
  SCC { #7 }
only weak rules.
Number of SCCs: 0, DPs: 0
Next Dependency Pairs:
     #17: #+(+(s(x),s(y)),_1) -> #+(s(s(+(x,y))),_1)
     #18: #U(x,U(y,z)) ->= #U(U(x,y),z)
     #19: #U(x,U(y,z)) ->= #U(x,y)
     #20: #+(x,+(y,z)) ->= #+(+(x,y),z)
     #21: #+(x,+(y,z)) ->= #+(x,y)
     #22: #*(x,*(y,z)) ->= #*(*(x,y),z)
     #23: #*(x,*(y,z)) ->= #*(x,y)
     #24: #U(U(empty(),b),_1) -> #U(b,_1)
     #25: #*(*(0(),x),_1) -> #*(0(),_1)
     #26: #+(+(0(),x),_1) -> #+(x,_1)
     #27: #*(*(s(x),s(y)),_1) -> #*(s(+(+(x,y),*(x,y))),_1)
Number of SCCs: 3, DPs: 11
  SCC { #18 #19 #24 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: x1 + 1
      #prod	w: 0
      #* 	w: 0
      #U 	w: x1 + x2
      sum	w: 0
      0 	w: 1
      singl	w: 0
      empty	w: 62898
      + 	w: x1 + x2 + 1
      #sum	w: 0
      U 	w: x1 + x2 + 1
      #+ 	w: x1 + x2
      * 	w: x1 + x2 + 10450
    USABLE RULES: { 1 2 5 12 13 }
    Removed DPs: #19 #24
Number of SCCs: 3, DPs: 9
  SCC { #18 }
only weak rules.
Number of SCCs: 2, DPs: 8
  SCC { #22 #23 #25 #27 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: 2
      #prod	w: 0
      #* 	w: x1 + x2
      #U 	w: x1 + x2
      sum	w: 0
      0 	w: 1
      singl	w: 0
      empty	w: 1
      + 	w: 1
      #sum	w: 0
      U 	w: x1 + x2 + 1
      #+ 	w: 0
      * 	w: x1 + x2 + 10450
    USABLE RULES: { 3..5 13 14 }
    Removed DPs: #23 #25 #27
Number of SCCs: 2, DPs: 5
  SCC { #22 }
only weak rules.
Number of SCCs: 1, DPs: 4
  SCC { #17 #20 #21 #26 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: x1 + 52572
      #prod	w: 0
      #* 	w: 0
      #U 	w: x1 + x2
      sum	w: 0
      0 	w: 1
      singl	w: 0
      empty	w: 1
      + 	w: x1 + x2 + 26286
      #sum	w: 0
      U 	w: x1 + x2 + 1
      #+ 	w: x1 + x2
      * 	w: x1 + x2
    USABLE RULES: { 1..3 5 12 13 }
    Removed DPs: #21 #26
Number of SCCs: 1, DPs: 2
  SCC { #17 #20 }
POLO(Sum)... succeeded.
      prod	w: 0
      s 	w: 14681
      #prod	w: 0
      #* 	w: 0
      #U 	w: x1 + x2
      sum	w: 0
      0 	w: 1
      singl	w: 0
      empty	w: 1
      + 	w: x1 + x2 + 1
      #sum	w: 0
      U 	w: x1 + x2 + 1
      #+ 	w: x1 + x2
      * 	w: 14681
    USABLE RULES: { 1..3 5 12 13 }
    Removed DPs: #17
Number of SCCs: 1, DPs: 1
  SCC { #20 }
only weak rules.
Number of SCCs: 0, DPs: 0