YES(?,O(n^2)) Problem: g(x,a(),b()) -> g(b(),b(),a()) Proof: Complexity Transformation Processor: strict: g(x,a(),b()) -> g(b(),b(),a()) weak: Matrix Interpretation Processor: dimension: 2 max_matrix: [1 1] [0 0] interpretation: [1 0] [1 0] [1 1] [g](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [0] [b] = [1], [0] [a] = [0] orientation: [1 0] [1] [0] g(x,a(),b()) = [0 0]x + [0] >= [0] = g(b(),b(),a()) problem: strict: weak: g(x,a(),b()) -> g(b(),b(),a()) Qed