MAYBE Problem: a(b(x)) -> b(a(a(x))) b(c(x)) -> c(b(b(x))) c(a(x)) -> a(c(c(x))) u(a(x)) -> x v(b(x)) -> x w(c(x)) -> x a(u(x)) -> x b(v(x)) -> x c(w(x)) -> x Proof: Complexity Transformation Processor: strict: a(b(x)) -> b(a(a(x))) b(c(x)) -> c(b(b(x))) c(a(x)) -> a(c(c(x))) u(a(x)) -> x v(b(x)) -> x w(c(x)) -> x a(u(x)) -> x b(v(x)) -> x c(w(x)) -> x weak: Matrix Interpretation Processor: dimension: 1 max_matrix: 1 interpretation: [w](x0) = x0 + 1, [v](x0) = x0, [u](x0) = x0 + 1, [c](x0) = x0, [a](x0) = x0, [b](x0) = x0 orientation: a(b(x)) = x >= x = b(a(a(x))) b(c(x)) = x >= x = c(b(b(x))) c(a(x)) = x >= x = a(c(c(x))) u(a(x)) = x + 1 >= x = x v(b(x)) = x >= x = x w(c(x)) = x + 1 >= x = x a(u(x)) = x + 1 >= x = x b(v(x)) = x >= x = x c(w(x)) = x + 1 >= x = x problem: strict: a(b(x)) -> b(a(a(x))) b(c(x)) -> c(b(b(x))) c(a(x)) -> a(c(c(x))) v(b(x)) -> x b(v(x)) -> x weak: u(a(x)) -> x w(c(x)) -> x a(u(x)) -> x c(w(x)) -> x Matrix Interpretation Processor: dimension: 1 max_matrix: 1 interpretation: [w](x0) = x0, [v](x0) = x0 + 1, [u](x0) = x0, [c](x0) = x0, [a](x0) = x0, [b](x0) = x0 orientation: a(b(x)) = x >= x = b(a(a(x))) b(c(x)) = x >= x = c(b(b(x))) c(a(x)) = x >= x = a(c(c(x))) v(b(x)) = x + 1 >= x = x b(v(x)) = x + 1 >= x = x u(a(x)) = x >= x = x w(c(x)) = x >= x = x a(u(x)) = x >= x = x c(w(x)) = x >= x = x problem: strict: a(b(x)) -> b(a(a(x))) b(c(x)) -> c(b(b(x))) c(a(x)) -> a(c(c(x))) weak: v(b(x)) -> x b(v(x)) -> x u(a(x)) -> x w(c(x)) -> x a(u(x)) -> x c(w(x)) -> x Open