YES Problem: f(x,y) -> g1(x,x,y) f(x,y) -> g1(y,x,x) f(x,y) -> g2(x,y,y) f(x,y) -> g2(y,y,x) g1(x,x,y) -> h(x,y) g1(y,x,x) -> h(x,y) g2(x,y,y) -> h(x,y) g2(y,y,x) -> h(x,y) h(x,x) -> x Proof: Polynomial Interpretation Processor: dimension: 1 interpretation: [h](x0, x1) = -1x0 + 2x1 + 2x0x0 + 2x1x1 + 1, [g2](x0, x1, x2) = x0 + x1 + x2 + 2x0x0 + 2x2x2 + 2, [g1](x0, x1, x2) = 2x0 + -3x1 + 2x2 + 2x0x0 + 4x1x1 + 2x2x2 + 2, [f](x0, x1) = x0 + 2x1 + 6x0x0 + 2x1x1 + 7 orientation: f(x,y) = x + 6x*x + 2y + 2y*y + 7 >= -1x + 6x*x + 2y + 2y*y + 2 = g1(x,x,y) f(x,y) = x + 6x*x + 2y + 2y*y + 7 >= -1x + 6x*x + 2y + 2y*y + 2 = g1(y,x,x) f(x,y) = x + 6x*x + 2y + 2y*y + 7 >= x + 2x*x + 2y + 2y*y + 2 = g2(x,y,y) f(x,y) = x + 6x*x + 2y + 2y*y + 7 >= x + 2x*x + 2y + 2y*y + 2 = g2(y,y,x) g1(x,x,y) = -1x + 6x*x + 2y + 2y*y + 2 >= -1x + 2x*x + 2y + 2y*y + 1 = h(x,y) g1(y,x,x) = -1x + 6x*x + 2y + 2y*y + 2 >= -1x + 2x*x + 2y + 2y*y + 1 = h(x,y) g2(x,y,y) = x + 2x*x + 2y + 2y*y + 2 >= -1x + 2x*x + 2y + 2y*y + 1 = h(x,y) g2(y,y,x) = x + 2x*x + 2y + 2y*y + 2 >= -1x + 2x*x + 2y + 2y*y + 1 = h(x,y) h(x,x) = x + 4x*x + 1 >= x = x problem: Qed