YES(?,O(n^1)) 0.16/0.22 YES(?,O(n^1)) 0.16/0.22 0.16/0.22 Problem: 0.16/0.22 f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v)) 0.16/0.22 f(x,y,y) -> y 0.16/0.22 f(x,y,g(y)) -> x 0.16/0.22 f(x,x,y) -> x 0.16/0.22 f(g(x),x,y) -> y 0.16/0.22 0.16/0.22 Proof: 0.16/0.22 Complexity Transformation Processor: 0.16/0.22 strict: 0.16/0.22 f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v)) 0.16/0.22 f(x,y,y) -> y 0.16/0.22 f(x,y,g(y)) -> x 0.16/0.22 f(x,x,y) -> x 0.16/0.22 f(g(x),x,y) -> y 0.16/0.22 weak: 0.16/0.22 0.16/0.22 Matrix Interpretation Processor: dim=1 0.16/0.22 0.16/0.22 max_matrix: 0.16/0.22 1 0.16/0.22 interpretation: 0.16/0.22 [g](x0) = x0 + 192, 0.16/0.22 0.16/0.22 [f](x0, x1, x2) = x0 + x1 + x2 + 33 0.16/0.22 orientation: 0.16/0.22 f(f(x,y,z),u,f(x,y,v)) = u + v + 2x + 2y + z + 99 >= u + v + x + y + z + 66 = f(x,y,f(z,u,v)) 0.16/0.22 0.16/0.22 f(x,y,y) = x + 2y + 33 >= y = y 0.16/0.22 0.16/0.22 f(x,y,g(y)) = x + 2y + 225 >= x = x 0.16/0.22 0.16/0.22 f(x,x,y) = 2x + y + 33 >= x = x 0.16/0.22 0.16/0.22 f(g(x),x,y) = 2x + y + 225 >= y = y 0.16/0.22 problem: 0.16/0.22 strict: 0.16/0.22 0.16/0.22 weak: 0.16/0.22 f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v)) 0.16/0.22 f(x,y,y) -> y 0.16/0.22 f(x,y,g(y)) -> x 0.16/0.22 f(x,x,y) -> x 0.16/0.22 f(g(x),x,y) -> y 0.16/0.22 Qed 0.16/0.23 EOF