YES(?,O(n^2)) 15.69/7.24 YES(?,O(n^2)) 15.69/7.25 15.69/7.25 Problem: 15.69/7.25 g(f(x,y),z) -> f(x,g(y,z)) 15.69/7.25 g(h(x,y),z) -> g(x,f(y,z)) 15.69/7.25 g(x,h(y,z)) -> h(g(x,y),z) 15.69/7.25 15.69/7.25 Proof: 15.69/7.25 Complexity Transformation Processor: 15.69/7.25 strict: 15.69/7.25 g(f(x,y),z) -> f(x,g(y,z)) 15.69/7.25 g(h(x,y),z) -> g(x,f(y,z)) 15.69/7.25 g(x,h(y,z)) -> h(g(x,y),z) 15.69/7.25 weak: 15.69/7.25 15.69/7.25 Matrix Interpretation Processor: dim=1 15.69/7.25 15.69/7.25 max_matrix: 15.69/7.25 1 15.69/7.25 interpretation: 15.69/7.25 [h](x0, x1) = x0 + x1 + 200, 15.69/7.25 15.69/7.25 [g](x0, x1) = x0 + x1, 15.69/7.25 15.69/7.25 [f](x0, x1) = x0 + x1 + 32 15.69/7.25 orientation: 15.69/7.25 g(f(x,y),z) = x + y + z + 32 >= x + y + z + 32 = f(x,g(y,z)) 15.69/7.25 15.69/7.25 g(h(x,y),z) = x + y + z + 200 >= x + y + z + 32 = g(x,f(y,z)) 15.69/7.25 15.69/7.25 g(x,h(y,z)) = x + y + z + 200 >= x + y + z + 200 = h(g(x,y),z) 15.69/7.25 problem: 15.69/7.25 strict: 15.69/7.25 g(f(x,y),z) -> f(x,g(y,z)) 15.69/7.25 g(x,h(y,z)) -> h(g(x,y),z) 15.69/7.25 weak: 15.69/7.25 g(h(x,y),z) -> g(x,f(y,z)) 15.69/7.25 Matrix Interpretation Processor: dim=4 15.69/7.25 15.69/7.25 max_matrix: 15.69/7.25 [1 1 0 0] 15.69/7.25 [0 1 1 0] 15.69/7.25 [0 0 0 1] 15.69/7.25 [0 0 0 0] 15.69/7.25 interpretation: 15.69/7.25 [1 0 0 0] [1 1 0 0] [1] 15.69/7.25 [0 1 0 0] [0 0 0 0] [0] 15.69/7.25 [h](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1 + [0] 15.69/7.25 [0 0 0 0] [0 0 0 0] [0], 15.69/7.25 15.69/7.25 [1 1 0 0] [1 0 0 0] 15.69/7.25 [0 1 0 0] [0 0 0 0] 15.69/7.25 [g](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1 15.69/7.25 [0 0 0 0] [0 0 0 0] , 15.69/7.25 15.69/7.25 [1 1 0 0] [1 0 0 0] [0] 15.69/7.25 [0 1 1 0] [0 1 1 0] [1] 15.69/7.25 [f](x0, x1) = [0 0 0 0]x0 + [0 0 0 1]x1 + [0] 15.69/7.25 [0 0 0 0] [0 0 0 0] [0] 15.69/7.25 orientation: 15.69/7.25 [1 2 1 0] [1 1 1 0] [1 0 0 0] [1] [1 1 0 0] [1 1 0 0] [1 0 0 0] [0] 15.69/7.25 [0 1 1 0] [0 1 1 0] [0 0 0 0] [1] [0 1 1 0] [0 1 0 0] [0 0 0 0] [1] 15.69/7.25 g(f(x,y),z) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] = f(x,g(y,z)) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] 15.69/7.25 15.69/7.25 [1 1 0 0] [1 0 0 0] [1 1 0 0] [1] [1 1 0 0] [1 0 0 0] [1 1 0 0] [1] 15.69/7.25 [0 1 0 0] [0 0 0 0] [0 0 0 0] [0] [0 1 0 0] [0 0 0 0] [0 0 0 0] [0] 15.69/7.25 g(x,h(y,z)) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] = h(g(x,y),z) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] 15.69/7.25 15.69/7.25 [1 1 0 0] [1 1 0 0] [1 0 0 0] [1] [1 1 0 0] [1 1 0 0] [1 0 0 0] 15.69/7.25 [0 1 0 0] [0 0 0 0] [0 0 0 0] [0] [0 1 0 0] [0 0 0 0] [0 0 0 0] 15.69/7.25 g(h(x,y),z) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z = g(x,f(y,z)) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] [0 0 0 0] [0 0 0 0] [0 0 0 0] 15.69/7.25 problem: 15.69/7.25 strict: 15.69/7.25 g(x,h(y,z)) -> h(g(x,y),z) 15.69/7.25 weak: 15.69/7.25 g(f(x,y),z) -> f(x,g(y,z)) 15.69/7.25 g(h(x,y),z) -> g(x,f(y,z)) 15.69/7.25 Matrix Interpretation Processor: dim=4 15.69/7.25 15.69/7.25 max_matrix: 15.69/7.25 [1 1 1 1] 15.69/7.25 [0 1 0 0] 15.69/7.25 [0 0 0 0] 15.69/7.25 [0 0 0 0] 15.69/7.25 interpretation: 15.69/7.25 [1 0 0 0] [1 0 1 1] [0] 15.69/7.25 [0 1 0 0] [0 0 0 0] [1] 15.69/7.25 [h](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1 + [0] 15.69/7.25 [0 0 0 0] [0 0 0 0] [0], 15.69/7.25 15.69/7.25 [1 0 0 0] [1 1 0 0] [0] 15.69/7.25 [0 0 0 0] [0 1 0 0] [0] 15.69/7.25 [g](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1 + [1] 15.69/7.25 [0 0 0 0] [0 0 0 0] [1], 15.69/7.25 15.69/7.25 [1 0 1 1] [1 0 0 0] 15.69/7.25 [0 0 0 0] [0 1 0 0] 15.69/7.25 [f](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1 15.69/7.25 [0 0 0 0] [0 0 0 0] 15.69/7.25 orientation: 15.69/7.25 [1 0 0 0] [1 1 0 0] [1 0 1 1] [1] [1 0 0 0] [1 1 0 0] [1 0 1 1] [0] 15.69/7.25 [0 0 0 0] [0 1 0 0] [0 0 0 0] [1] [0 0 0 0] [0 1 0 0] [0 0 0 0] [1] 15.69/7.25 g(x,h(y,z)) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [1] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [0] = h(g(x,y),z) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [1] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0] 15.69/7.25 15.69/7.25 [1 0 1 1] [1 0 0 0] [1 1 0 0] [0] [1 0 1 1] [1 0 0 0] [1 1 0 0] 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 1 0 0] [0] [0 0 0 0] [0 0 0 0] [0 1 0 0] 15.69/7.25 g(f(x,y),z) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [1] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z = f(x,g(y,z)) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [1] [0 0 0 0] [0 0 0 0] [0 0 0 0] 15.69/7.25 15.69/7.25 [1 0 0 0] [1 0 1 1] [1 1 0 0] [0] [1 0 0 0] [1 0 1 1] [1 1 0 0] [0] 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 1 0 0] [0] [0 0 0 0] [0 0 0 0] [0 1 0 0] [0] 15.69/7.25 g(h(x,y),z) = [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [1] >= [0 0 0 0]x + [0 0 0 0]y + [0 0 0 0]z + [1] = g(x,f(y,z)) 15.69/7.25 [0 0 0 0] [0 0 0 0] [0 0 0 0] [1] [0 0 0 0] [0 0 0 0] [0 0 0 0] [1] 15.69/7.25 problem: 15.69/7.25 strict: 15.69/7.25 15.69/7.25 weak: 15.69/7.25 g(x,h(y,z)) -> h(g(x,y),z) 15.69/7.25 g(f(x,y),z) -> f(x,g(y,z)) 15.69/7.25 g(h(x,y),z) -> g(x,f(y,z)) 15.69/7.25 Qed 15.69/7.26 EOF