MAYBE Problem: f(a()) -> f(c(a())) f(c(X)) -> X f(c(a())) -> f(d(b())) f(a()) -> f(d(a())) f(d(X)) -> X f(c(b())) -> f(d(a())) e(g(X)) -> e(X) Proof: Complexity Transformation Processor: strict: f(a()) -> f(c(a())) f(c(X)) -> X f(c(a())) -> f(d(b())) f(a()) -> f(d(a())) f(d(X)) -> X f(c(b())) -> f(d(a())) e(g(X)) -> e(X) weak: Matrix Interpretation Processor: dimension: 1 max_matrix: 1 interpretation: [e](x0) = x0 + 1, [g](x0) = x0 + 1, [d](x0) = x0, [b] = 0, [c](x0) = x0, [f](x0) = x0, [a] = 0 orientation: f(a()) = 0 >= 0 = f(c(a())) f(c(X)) = X >= X = X f(c(a())) = 0 >= 0 = f(d(b())) f(a()) = 0 >= 0 = f(d(a())) f(d(X)) = X >= X = X f(c(b())) = 0 >= 0 = f(d(a())) e(g(X)) = X + 2 >= X + 1 = e(X) problem: strict: f(a()) -> f(c(a())) f(c(X)) -> X f(c(a())) -> f(d(b())) f(a()) -> f(d(a())) f(d(X)) -> X f(c(b())) -> f(d(a())) weak: e(g(X)) -> e(X) Matrix Interpretation Processor: dimension: 1 max_matrix: 1 interpretation: [e](x0) = x0, [g](x0) = x0, [d](x0) = x0, [b] = 0, [c](x0) = x0 + 1, [f](x0) = x0, [a] = 0 orientation: f(a()) = 0 >= 1 = f(c(a())) f(c(X)) = X + 1 >= X = X f(c(a())) = 1 >= 0 = f(d(b())) f(a()) = 0 >= 0 = f(d(a())) f(d(X)) = X >= X = X f(c(b())) = 1 >= 0 = f(d(a())) e(g(X)) = X >= X = e(X) problem: strict: f(a()) -> f(c(a())) f(a()) -> f(d(a())) f(d(X)) -> X weak: f(c(X)) -> X f(c(a())) -> f(d(b())) f(c(b())) -> f(d(a())) e(g(X)) -> e(X) Matrix Interpretation Processor: dimension: 1 max_matrix: 1 interpretation: [e](x0) = x0, [g](x0) = x0, [d](x0) = x0 + 1, [b] = 0, [c](x0) = x0 + 1, [f](x0) = x0, [a] = 0 orientation: f(a()) = 0 >= 1 = f(c(a())) f(a()) = 0 >= 1 = f(d(a())) f(d(X)) = X + 1 >= X = X f(c(X)) = X + 1 >= X = X f(c(a())) = 1 >= 1 = f(d(b())) f(c(b())) = 1 >= 1 = f(d(a())) e(g(X)) = X >= X = e(X) problem: strict: f(a()) -> f(c(a())) f(a()) -> f(d(a())) weak: f(d(X)) -> X f(c(X)) -> X f(c(a())) -> f(d(b())) f(c(b())) -> f(d(a())) e(g(X)) -> e(X) Open