YES(?,O(n^4)) 157.07/74.22 YES(?,O(n^4)) 157.07/74.23 157.07/74.23 Problem: 157.07/74.23 a(x1) -> b(c(x1)) 157.07/74.23 a(b(x1)) -> b(a(x1)) 157.07/74.23 d(c(x1)) -> d(a(x1)) 157.07/74.23 a(c(x1)) -> c(a(x1)) 157.07/74.23 157.07/74.23 Proof: 157.07/74.23 Complexity Transformation Processor: 157.07/74.23 strict: 157.07/74.23 a(x1) -> b(c(x1)) 157.07/74.23 a(b(x1)) -> b(a(x1)) 157.07/74.23 d(c(x1)) -> d(a(x1)) 157.07/74.23 a(c(x1)) -> c(a(x1)) 157.07/74.23 weak: 157.07/74.23 157.07/74.23 Matrix Interpretation Processor: dim=1 157.07/74.23 157.07/74.23 max_matrix: 157.07/74.23 1 157.07/74.23 interpretation: 157.07/74.23 [d](x0) = x0 + 220, 157.07/74.23 157.07/74.23 [b](x0) = x0 + 73, 157.07/74.23 157.07/74.23 [c](x0) = x0 + 24, 157.07/74.23 157.07/74.23 [a](x0) = x0 + 168 157.07/74.23 orientation: 157.07/74.23 a(x1) = x1 + 168 >= x1 + 97 = b(c(x1)) 157.07/74.23 157.07/74.23 a(b(x1)) = x1 + 241 >= x1 + 241 = b(a(x1)) 157.07/74.23 157.07/74.23 d(c(x1)) = x1 + 244 >= x1 + 388 = d(a(x1)) 157.07/74.23 157.07/74.23 a(c(x1)) = x1 + 192 >= x1 + 192 = c(a(x1)) 157.07/74.23 problem: 157.07/74.23 strict: 157.07/74.23 a(b(x1)) -> b(a(x1)) 157.07/74.23 d(c(x1)) -> d(a(x1)) 157.07/74.23 a(c(x1)) -> c(a(x1)) 157.07/74.23 weak: 157.07/74.23 a(x1) -> b(c(x1)) 157.07/74.23 Matrix Interpretation Processor: dim=4 157.07/74.23 157.07/74.23 max_matrix: 157.07/74.23 [1 0 1 1] 157.07/74.23 [0 0 1 1] 157.07/74.23 [0 0 1 1] 157.07/74.23 [0 0 0 1] 157.07/74.23 interpretation: 157.07/74.23 [1 0 1 1] [1] 157.07/74.23 [0 0 0 0] [0] 157.07/74.23 [d](x0) = [0 0 0 0]x0 + [0] 157.07/74.23 [0 0 0 0] [0], 157.07/74.23 157.07/74.23 [1 0 0 1] 157.07/74.23 [0 0 0 0] 157.07/74.23 [b](x0) = [0 0 0 0]x0 157.07/74.23 [0 0 0 0] , 157.07/74.23 157.07/74.23 [1 0 0 0] [0] 157.07/74.23 [0 0 0 0] [0] 157.07/74.23 [c](x0) = [0 0 1 1]x0 + [1] 157.07/74.23 [0 0 0 0] [1], 157.07/74.23 157.07/74.23 [1 0 0 0] [1] 157.07/74.23 [0 0 1 1] [0] 157.07/74.23 [a](x0) = [0 0 1 0]x0 + [0] 157.07/74.23 [0 0 0 1] [0] 157.07/74.23 orientation: 157.07/74.23 [1 0 0 1] [1] [1 0 0 1] [1] 157.07/74.23 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.23 a(b(x1)) = [0 0 0 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(a(x1)) 157.07/74.23 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.23 157.07/74.23 [1 0 1 1] [3] [1 0 1 1] [2] 157.07/74.23 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.23 d(c(x1)) = [0 0 0 0]x1 + [0] >= [0 0 0 0]x1 + [0] = d(a(x1)) 157.07/74.23 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.23 157.07/74.23 [1 0 0 0] [1] [1 0 0 0] [1] 157.07/74.23 [0 0 1 1] [2] [0 0 0 0] [0] 157.07/74.23 a(c(x1)) = [0 0 1 1]x1 + [1] >= [0 0 1 1]x1 + [1] = c(a(x1)) 157.07/74.23 [0 0 0 0] [1] [0 0 0 0] [1] 157.07/74.23 157.07/74.23 [1 0 0 0] [1] [1 0 0 0] [1] 157.07/74.23 [0 0 1 1] [0] [0 0 0 0] [0] 157.07/74.23 a(x1) = [0 0 1 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(c(x1)) 157.07/74.23 [0 0 0 1] [0] [0 0 0 0] [0] 157.07/74.23 problem: 157.07/74.23 strict: 157.07/74.23 a(b(x1)) -> b(a(x1)) 157.07/74.23 a(c(x1)) -> c(a(x1)) 157.07/74.23 weak: 157.07/74.23 d(c(x1)) -> d(a(x1)) 157.07/74.23 a(x1) -> b(c(x1)) 157.07/74.23 Matrix Interpretation Processor: dim=4 157.07/74.23 157.07/74.23 max_matrix: 157.07/74.23 [1 1 0 1] 157.07/74.23 [0 1 1 1] 157.07/74.23 [0 0 1 0] 157.07/74.23 [0 0 0 1] 157.07/74.23 interpretation: 157.07/74.23 [1 1 0 0] [1] 157.07/74.23 [0 1 0 0] [0] 157.07/74.23 [d](x0) = [0 0 0 0]x0 + [1] 157.07/74.23 [0 0 0 0] [0], 157.07/74.23 157.07/74.23 [1 0 0 0] [0] 157.07/74.23 [0 0 0 0] [0] 157.07/74.23 [b](x0) = [0 0 0 0]x0 + [0] 157.07/74.23 [0 0 0 1] [1], 157.07/74.23 157.07/74.23 [1 0 0 0] [0] 157.07/74.23 [0 1 1 1] [0] 157.07/74.23 [c](x0) = [0 0 1 0]x0 + [1] 157.07/74.23 [0 0 0 1] [0], 157.07/74.23 157.07/74.23 [1 0 0 1] [0] 157.07/74.23 [0 1 1 0] [0] 157.07/74.23 [a](x0) = [0 0 1 0]x0 + [0] 157.07/74.23 [0 0 0 1] [1] 157.07/74.23 orientation: 157.07/74.23 [1 0 0 1] [1] [1 0 0 1] [0] 157.07/74.23 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.23 a(b(x1)) = [0 0 0 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(a(x1)) 157.07/74.23 [0 0 0 1] [2] [0 0 0 1] [2] 157.07/74.23 157.07/74.23 [1 0 0 1] [0] [1 0 0 1] [0] 157.07/74.23 [0 1 2 1] [1] [0 1 2 1] [1] 157.07/74.23 a(c(x1)) = [0 0 1 0]x1 + [1] >= [0 0 1 0]x1 + [1] = c(a(x1)) 157.07/74.23 [0 0 0 1] [1] [0 0 0 1] [1] 157.07/74.23 157.07/74.23 [1 1 1 1] [1] [1 1 1 1] [1] 157.07/74.23 [0 1 1 1] [0] [0 1 1 0] [0] 157.07/74.24 d(c(x1)) = [0 0 0 0]x1 + [1] >= [0 0 0 0]x1 + [1] = d(a(x1)) 157.07/74.24 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.24 157.07/74.24 [1 0 0 1] [0] [1 0 0 0] [0] 157.07/74.24 [0 1 1 0] [0] [0 0 0 0] [0] 157.07/74.24 a(x1) = [0 0 1 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(c(x1)) 157.07/74.24 [0 0 0 1] [1] [0 0 0 1] [1] 157.07/74.24 problem: 157.07/74.24 strict: 157.07/74.24 a(c(x1)) -> c(a(x1)) 157.07/74.24 weak: 157.07/74.24 a(b(x1)) -> b(a(x1)) 157.07/74.24 d(c(x1)) -> d(a(x1)) 157.07/74.24 a(x1) -> b(c(x1)) 157.07/74.24 Matrix Interpretation Processor: dim=4 157.07/74.24 157.07/74.24 max_matrix: 157.07/74.24 [1 1 0 1] 157.07/74.24 [0 1 1 1] 157.07/74.24 [0 0 1 1] 157.07/74.24 [0 0 0 1] 157.07/74.24 interpretation: 157.07/74.24 [1 1 0 0] [1] 157.07/74.24 [0 1 0 0] [0] 157.07/74.24 [d](x0) = [0 0 0 1]x0 + [0] 157.07/74.24 [0 0 0 0] [1], 157.07/74.24 157.07/74.24 [1 0 0 0] 157.07/74.24 [0 0 0 0] 157.07/74.24 [b](x0) = [0 0 0 0]x0 157.07/74.24 [0 0 0 1] , 157.07/74.24 157.07/74.24 [1 0 0 0] [0] 157.07/74.24 [0 1 1 1] [0] 157.07/74.24 [c](x0) = [0 0 1 0]x0 + [1] 157.07/74.24 [0 0 0 1] [1], 157.07/74.24 157.07/74.24 [1 0 0 1] [0] 157.07/74.24 [0 1 1 0] [0] 157.07/74.24 [a](x0) = [0 0 1 0]x0 + [0] 157.07/74.24 [0 0 0 1] [1] 157.07/74.24 orientation: 157.07/74.24 [1 0 0 1] [1] [1 0 0 1] [0] 157.07/74.24 [0 1 2 1] [1] [0 1 2 1] [1] 157.07/74.24 a(c(x1)) = [0 0 1 0]x1 + [1] >= [0 0 1 0]x1 + [1] = c(a(x1)) 157.07/74.24 [0 0 0 1] [2] [0 0 0 1] [2] 157.07/74.24 157.07/74.24 [1 0 0 1] [0] [1 0 0 1] [0] 157.07/74.24 [0 0 0 0] [0] [0 0 0 0] [0] 157.07/74.24 a(b(x1)) = [0 0 0 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(a(x1)) 157.07/74.24 [0 0 0 1] [1] [0 0 0 1] [1] 157.07/74.24 157.07/74.24 [1 1 1 1] [1] [1 1 1 1] [1] 157.07/74.24 [0 1 1 1] [0] [0 1 1 0] [0] 157.07/74.24 d(c(x1)) = [0 0 0 1]x1 + [1] >= [0 0 0 1]x1 + [1] = d(a(x1)) 157.07/74.24 [0 0 0 0] [1] [0 0 0 0] [1] 157.07/74.24 157.07/74.24 [1 0 0 1] [0] [1 0 0 0] [0] 157.07/74.24 [0 1 1 0] [0] [0 0 0 0] [0] 157.07/74.24 a(x1) = [0 0 1 0]x1 + [0] >= [0 0 0 0]x1 + [0] = b(c(x1)) 157.07/74.24 [0 0 0 1] [1] [0 0 0 1] [1] 157.07/74.24 problem: 157.07/74.24 strict: 157.07/74.24 157.07/74.24 weak: 157.07/74.24 a(c(x1)) -> c(a(x1)) 157.07/74.24 a(b(x1)) -> b(a(x1)) 157.07/74.24 d(c(x1)) -> d(a(x1)) 157.07/74.24 a(x1) -> b(c(x1)) 157.07/74.24 Qed 157.07/74.24 EOF