YES(?,O(n^2)) 20.92/7.41 YES(?,O(n^2)) 20.92/7.41 20.92/7.41 Problem: 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 activate(X) -> X 20.92/7.41 20.92/7.41 Proof: 20.92/7.41 Complexity Transformation Processor: 20.92/7.41 strict: 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 activate(X) -> X 20.92/7.41 weak: 20.92/7.41 20.92/7.41 Matrix Interpretation Processor: dim=1 20.92/7.41 20.92/7.41 max_matrix: 20.92/7.41 1 20.92/7.41 interpretation: 20.92/7.41 [activate](x0) = x0 + 9, 20.92/7.41 20.92/7.41 [g](x0) = x0 + 248, 20.92/7.41 20.92/7.41 [c](x0) = x0 + 8, 20.92/7.41 20.92/7.41 [n__g](x0) = x0 + 226, 20.92/7.41 20.92/7.41 [n__f](x0) = x0 + 1, 20.92/7.41 20.92/7.41 [n__a] = 69, 20.92/7.41 20.92/7.41 [f](x0) = x0 + 92, 20.92/7.41 20.92/7.41 [a] = 132 20.92/7.41 orientation: 20.92/7.41 f(f(a())) = 316 >= 305 = c(n__f(n__g(n__f(n__a())))) 20.92/7.41 20.92/7.41 f(X) = X + 92 >= X + 1 = n__f(X) 20.92/7.41 20.92/7.41 g(X) = X + 248 >= X + 226 = n__g(X) 20.92/7.41 20.92/7.41 a() = 132 >= 69 = n__a() 20.92/7.41 20.92/7.41 activate(n__f(X)) = X + 10 >= X + 101 = f(activate(X)) 20.92/7.41 20.92/7.41 activate(n__g(X)) = X + 235 >= X + 257 = g(activate(X)) 20.92/7.41 20.92/7.41 activate(n__a()) = 78 >= 132 = a() 20.92/7.41 20.92/7.41 activate(X) = X + 9 >= X = X 20.92/7.41 problem: 20.92/7.41 strict: 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 weak: 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(X) -> X 20.92/7.41 Matrix Interpretation Processor: dim=1 20.92/7.41 20.92/7.41 max_matrix: 20.92/7.41 1 20.92/7.41 interpretation: 20.92/7.41 [activate](x0) = x0 + 144, 20.92/7.41 20.92/7.41 [g](x0) = x0 + 69, 20.92/7.41 20.92/7.41 [c](x0) = x0 + 161, 20.92/7.41 20.92/7.41 [n__g](x0) = x0 + 21, 20.92/7.41 20.92/7.41 [n__f](x0) = x0, 20.92/7.41 20.92/7.41 [n__a] = 3, 20.92/7.41 20.92/7.41 [f](x0) = x0 + 128, 20.92/7.41 20.92/7.41 [a] = 128 20.92/7.41 orientation: 20.92/7.41 activate(n__f(X)) = X + 144 >= X + 272 = f(activate(X)) 20.92/7.41 20.92/7.41 activate(n__g(X)) = X + 165 >= X + 213 = g(activate(X)) 20.92/7.41 20.92/7.41 activate(n__a()) = 147 >= 128 = a() 20.92/7.41 20.92/7.41 f(f(a())) = 384 >= 185 = c(n__f(n__g(n__f(n__a())))) 20.92/7.41 20.92/7.41 f(X) = X + 128 >= X = n__f(X) 20.92/7.41 20.92/7.41 g(X) = X + 69 >= X + 21 = n__g(X) 20.92/7.41 20.92/7.41 a() = 128 >= 3 = n__a() 20.92/7.41 20.92/7.41 activate(X) = X + 144 >= X = X 20.92/7.41 problem: 20.92/7.41 strict: 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 weak: 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(X) -> X 20.92/7.41 Matrix Interpretation Processor: dim=2 20.92/7.41 20.92/7.41 max_matrix: 20.92/7.41 [1 2] 20.92/7.41 [0 1] 20.92/7.41 interpretation: 20.92/7.41 [1 1] [4] 20.92/7.41 [activate](x0) = [0 1]x0 + [0], 20.92/7.41 20.92/7.41 [3] 20.92/7.41 [g](x0) = x0 + [1], 20.92/7.41 20.92/7.41 [1 0] [0] 20.92/7.41 [c](x0) = [0 0]x0 + [2], 20.92/7.41 20.92/7.41 [3] 20.92/7.41 [n__g](x0) = x0 + [1], 20.92/7.41 20.92/7.41 [1 2] 20.92/7.41 [n__f](x0) = [0 1]x0, 20.92/7.41 20.92/7.41 [2] 20.92/7.41 [n__a] = [2], 20.92/7.41 20.92/7.41 [1 2] 20.92/7.41 [f](x0) = [0 1]x0, 20.92/7.41 20.92/7.41 [7] 20.92/7.41 [a] = [2] 20.92/7.41 orientation: 20.92/7.41 [1 3] [4] [1 3] [4] 20.92/7.41 activate(n__f(X)) = [0 1]X + [0] >= [0 1]X + [0] = f(activate(X)) 20.92/7.41 20.92/7.41 [1 1] [8] [1 1] [7] 20.92/7.41 activate(n__g(X)) = [0 1]X + [1] >= [0 1]X + [1] = g(activate(X)) 20.92/7.41 20.92/7.41 [8] [7] 20.92/7.41 activate(n__a()) = [2] >= [2] = a() 20.92/7.41 20.92/7.41 [15] [15] 20.92/7.41 f(f(a())) = [2 ] >= [2 ] = c(n__f(n__g(n__f(n__a())))) 20.92/7.41 20.92/7.41 [1 2] [1 2] 20.92/7.41 f(X) = [0 1]X >= [0 1]X = n__f(X) 20.92/7.41 20.92/7.41 [3] [3] 20.92/7.41 g(X) = X + [1] >= X + [1] = n__g(X) 20.92/7.41 20.92/7.41 [7] [2] 20.92/7.41 a() = [2] >= [2] = n__a() 20.92/7.41 20.92/7.41 [1 1] [4] 20.92/7.41 activate(X) = [0 1]X + [0] >= X = X 20.92/7.41 problem: 20.92/7.41 strict: 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 weak: 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(X) -> X 20.92/7.41 Matrix Interpretation Processor: dim=2 20.92/7.41 20.92/7.41 max_matrix: 20.92/7.41 [1 1] 20.92/7.41 [0 1] 20.92/7.41 interpretation: 20.92/7.41 [1 1] 20.92/7.41 [activate](x0) = [0 1]x0, 20.92/7.41 20.92/7.41 20.92/7.41 [g](x0) = x0, 20.92/7.41 20.92/7.41 [1 0] [0] 20.92/7.41 [c](x0) = [0 0]x0 + [6], 20.92/7.41 20.92/7.41 20.92/7.41 [n__g](x0) = x0, 20.92/7.41 20.92/7.41 [4] 20.92/7.41 [n__f](x0) = x0 + [3], 20.92/7.41 20.92/7.41 [4] 20.92/7.41 [n__a] = [0], 20.92/7.41 20.92/7.41 [4] 20.92/7.41 [f](x0) = x0 + [3], 20.92/7.41 20.92/7.41 [4] 20.92/7.41 [a] = [0] 20.92/7.41 orientation: 20.92/7.41 [1 1] [7] [1 1] [4] 20.92/7.41 activate(n__f(X)) = [0 1]X + [3] >= [0 1]X + [3] = f(activate(X)) 20.92/7.41 20.92/7.41 [1 1] [1 1] 20.92/7.41 activate(n__g(X)) = [0 1]X >= [0 1]X = g(activate(X)) 20.92/7.41 20.92/7.41 [4] [4] 20.92/7.41 activate(n__a()) = [0] >= [0] = a() 20.92/7.41 20.92/7.41 [12] [12] 20.92/7.41 f(f(a())) = [6 ] >= [6 ] = c(n__f(n__g(n__f(n__a())))) 20.92/7.41 20.92/7.41 [4] [4] 20.92/7.41 f(X) = X + [3] >= X + [3] = n__f(X) 20.92/7.41 20.92/7.41 20.92/7.41 g(X) = X >= X = n__g(X) 20.92/7.41 20.92/7.41 [4] [4] 20.92/7.41 a() = [0] >= [0] = n__a() 20.92/7.41 20.92/7.41 [1 1] 20.92/7.41 activate(X) = [0 1]X >= X = X 20.92/7.41 problem: 20.92/7.41 strict: 20.92/7.41 20.92/7.41 weak: 20.92/7.41 activate(n__f(X)) -> f(activate(X)) 20.92/7.41 activate(n__g(X)) -> g(activate(X)) 20.92/7.41 activate(n__a()) -> a() 20.92/7.41 f(f(a())) -> c(n__f(n__g(n__f(n__a())))) 20.92/7.41 f(X) -> n__f(X) 20.92/7.41 g(X) -> n__g(X) 20.92/7.41 a() -> n__a() 20.92/7.41 activate(X) -> X 20.92/7.41 Qed 20.92/7.42 EOF