YES Problem: s(a()) -> a() s(s(x)) -> x s(f(x,y)) -> f(s(y),s(x)) s(g(x,y)) -> g(s(x),s(y)) f(x,a()) -> x f(a(),y) -> y f(g(x,y),g(u,v)) -> g(f(x,u),f(y,v)) g(a(),a()) -> a() Proof: Matrix Interpretation Processor: dim=1 interpretation: [s](x0) = 4x0, [g](x0, x1) = 4x0 + 2x1 + 4, [a] = 0, [f](x0, x1) = x0 + x1 orientation: s(a()) = 0 >= 0 = a() s(s(x)) = 16x >= x = x s(f(x,y)) = 4x + 4y >= 4x + 4y = f(s(y),s(x)) s(g(x,y)) = 16x + 8y + 16 >= 16x + 8y + 4 = g(s(x),s(y)) f(x,a()) = x >= x = x f(a(),y) = y >= y = y f(g(x,y),g(u,v)) = 4u + 2v + 4x + 2y + 8 >= 4u + 2v + 4x + 2y + 4 = g(f(x,u),f(y,v)) g(a(),a()) = 4 >= 0 = a() problem: s(a()) -> a() s(s(x)) -> x s(f(x,y)) -> f(s(y),s(x)) f(x,a()) -> x f(a(),y) -> y Matrix Interpretation Processor: dim=1 interpretation: [s](x0) = 4x0 + 2, [a] = 2, [f](x0, x1) = 5x0 + 5x1 + 6 orientation: s(a()) = 10 >= 2 = a() s(s(x)) = 16x + 10 >= x = x s(f(x,y)) = 20x + 20y + 26 >= 20x + 20y + 26 = f(s(y),s(x)) f(x,a()) = 5x + 16 >= x = x f(a(),y) = 5y + 16 >= y = y problem: s(f(x,y)) -> f(s(y),s(x)) Matrix Interpretation Processor: dim=3 interpretation: [1 1 1] [s](x0) = [0 1 0]x0 [1 0 1] , [1 0 0] [1 0 0] [0] [f](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [1] [0 1 1] [0 1 1] [0] orientation: [1 1 1] [1 1 1] [1] [1 1 1] [1 1 1] [0] s(f(x,y)) = [0 0 0]x + [0 0 0]y + [1] >= [0 0 0]x + [0 0 0]y + [1] = f(s(y),s(x)) [1 1 1] [1 1 1] [0] [1 1 1] [1 1 1] [0] problem: Qed