YES O(n^2) TRS: {f(h(x)) -> f(i(x)), i(a()) -> b(), h(a()) -> b(), g(i(x)) -> g(h(x))} Natural interpretation: Strict: {f(h(x)) -> f(i(x)), i(a()) -> b(), h(a()) -> b(), g(i(x)) -> g(h(x))} Weak: {} Interpretation class: deltarestricted [a](delta) = + 2 + 0*delta [b](delta) = + 0 + 0*delta [g](delta, X0) = + 0*X0 + 0 + 1*X0*delta + 0*delta [h](delta, X0) = + 0*X0 + 1 + 2*X0*delta + 0*delta [i](delta, X0) = + 0*X0 + 0 + 2*X0*delta + 2*delta [f](delta, X0) = + 1*X0 + 0 + 3*X0*delta + 0*delta g_tau_1(delta) = delta/(0 + 1 * delta) h_tau_1(delta) = delta/(0 + 2 * delta) i_tau_1(delta) = delta/(0 + 2 * delta) f_tau_1(delta) = delta/(1 + 3 * delta) Qed