YES O(n^2) TRS: { g(x, h(y, z)) -> h(g(x, y), z), g(f(x, y), z) -> f(x, g(y, z)), g(h(x, y), z) -> g(x, f(y, z)) } Natural interpretation: Strict: { g(x, h(y, z)) -> h(g(x, y), z), g(f(x, y), z) -> f(x, g(y, z)), g(h(x, y), z) -> g(x, f(y, z)) } Weak: {} Interpretation class: deltarestricted [h](delta, X1, X0) = + 0*X0 + 1*X1 + 1 + 1*X0*delta + 0*X1*delta + 1*delta [g](delta, X1, X0) = + 1*X0 + 1*X1 + 0 + 1*X0*delta + 1*X1*delta + 0*delta [f](delta, X1, X0) = + 1*X0 + 0*X1 + 1 + 0*X0*delta + 1*X1*delta + 0*delta h_tau_1(delta) = delta/(1 + 0 * delta)h_tau_2(delta) = delta/(0 + 1 * delta) g_tau_1(delta) = delta/(1 + 1 * delta)g_tau_2(delta) = delta/(1 + 1 * delta) f_tau_1(delta) = delta/(0 + 1 * delta)f_tau_2(delta) = delta/(1 + 0 * delta) Qed