YES

TRS:

  g(0(),f(x,x)) -> x
  g(x,s(y)) -> g(f(x,y),0())
  g(s(x),y) -> g(f(x,y),0())
  g(f(x,y),0()) -> f(g(x,0()),g(y,0()))

linear polynomial interpretations on N:

  g_A(x1,x2) = x1 + x2
  g#_A(x1,x2) = x1 + x2
  0_A = 0
  0#_A = 0
  f_A(x1,x2) = x1 + x2 + 1
  f#_A(x1,x2) = x1 + x2 + 1
  s_A(x1) = x1 + 2
  s#_A(x1) = x1 + 2

precedence:

  g = s > f > 0