YES O(n^2) TRS: { f(X, X) -> c(X), f(X, c(X)) -> f(s(X), X), f(s(X), X) -> f(X, a(X))} Natural interpretation: Strict: { f(X, X) -> c(X), f(X, c(X)) -> f(s(X), X), f(s(X), X) -> f(X, a(X))} Weak: {} Interpretation class: deltarestricted [c](delta, X0) = + 0*X0 + 2 + 1*X0*delta + 0*delta [s](delta, X0) = + 0*X0 + 0 + 1*X0*delta + 1*delta [a](delta, X0) = + 0*X0 + 0 + 1*X0*delta + 0*delta [f](delta, X1, X0) = + 0*X0 + 0*X1 + 2 + 1*X0*delta + 1*X1*delta + 2*delta c_tau_1(delta) = delta/(0 + 1 * delta) s_tau_1(delta) = delta/(0 + 1 * delta) a_tau_1(delta) = delta/(0 + 1 * delta) f_tau_1(delta) = delta/(0 + 1 * delta)f_tau_2(delta) = delta/(0 + 1 * delta) Qed