YES O(n^2) TRS: { zeros() -> cons(0(), n__zeros()), zeros() -> n__zeros(), activate(X) -> X, activate(n__zeros()) -> zeros(), tail(cons(X, XS)) -> activate(XS) } Natural interpretation: Strict: { zeros() -> cons(0(), n__zeros()), zeros() -> n__zeros(), activate(X) -> X, activate(n__zeros()) -> zeros(), tail(cons(X, XS)) -> activate(XS) } Weak: {} Interpretation class: deltarestricted [tail](delta, X0) = + 1*X0 + 2 + 0*X0*delta + 3*delta [activate](delta, X0) = + 1*X0 + 2 + 0*X0*delta + 2*delta [zeros](delta) = + 0 + 1*delta [n__zeros](delta) = + 0 + 0*delta [0](delta) = + 0 + 0*delta [cons](delta, X1, X0) = + 1*X0 + 0*X1 + 0 + 0*X0*delta + 1*X1*delta + 0*delta tail_tau_1(delta) = delta/(1 + 0 * delta) activate_tau_1(delta) = delta/(1 + 0 * delta) cons_tau_1(delta) = delta/(0 + 1 * delta)cons_tau_2(delta) = delta/(1 + 0 * delta) Qed