YES
Input TRS:
      1: +(x,0()) -> x
      2: +(x,s(y)) -> s(+(x,y))
      3: +(0(),y) -> y
      4: +(s(x),y) -> s(+(x,y))
      5: +(x,+(y,z)) -> +(+(x,y),z)
      6: f(g(f(x))) -> f(h(s(0()),x))
      7: f(g(h(x,y))) -> f(h(s(x),y))
      8: f(h(x,h(y,z))) -> f(h(+(x,y),z))
Number of strict rules: 8
Direct POLO(bPol) ... removes: 8 1 3 5 7 6 2
      h 	w: 2 * x1 + 2 * x2 + 15927
      s 	w: x1 + 20538
      f 	w: 2 * x1 + 15927
      0 	w: 1
      + 	w: x1 + 2 * x2 + 15922
      g 	w: 2 * x1 + 25153
Number of strict rules: 1
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #+(s(x),y) -> #+(x,y)
Number of SCCs: 1, DPs: 1
  SCC { #1 }
POLO(Sum)... succeeded.
      h 	w: 0
      s 	w: x1 + 1
      f 	w: 0
      0 	w: 0
      + 	w: 0
      g 	w: 0
      #+ 	w: x1
    USABLE RULES: { }
    Removed DPs: #1
Number of SCCs: 0, DPs: 0