YES
Input TRS:
AC symbols: union
      1: union(empty(),X) -> X
      2: max(singl(x)) -> x
      3: max(union(singl(x),singl(0()))) -> x
      4: max(union(singl(s(x)),singl(s(y)))) -> s(max(union(singl(x),singl(y))))
      5: max(union(singl(x),union(Y,Z))) -> max(union(singl(x),singl(max(union(Y,Z)))))
Number of strict rules: 5
Direct POLO(bPol) ... removes: 4 1 3
      s 	w: x1 + 1
      0 	w: 23676
      max	w: x1
      union	w: x1 + x2 + 1
      singl	w: x1
      empty	w: 0
Number of strict rules: 2
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #max(union(singl(x),union(Y,Z))) -> #max(union(singl(x),singl(max(union(Y,Z)))))
     #2: #max(union(singl(x),union(Y,Z))) -> #max(union(Y,Z))
Number of SCCs: 1, DPs: 2
  SCC { #1 #2 }
POLO(Sum)... succeeded.
      s 	w: 0
      0 	w: 0
      max	w: x1
      union	w: x1 + x2 + 7759
      #max	w: x1
      singl	w: 7758
      empty	w: 0
    USABLE RULES: { 6 }
    Removed DPs: #1 #2
Number of SCCs: 0, DPs: 0
Next Dependency Pairs:
Number of SCCs: 0, DPs: 0