YES O(n^2) TRS: { app(app(app(curry(), f), x), y) -> app(app(f, x), y), app(app(plus(), app(s(), x)), y) -> app(s(), app(app(plus(), x), y)), app(app(plus(), 0()), y) -> y, add() -> app(curry(), plus()) } Natural interpretation: Strict: { app(app(app(curry(), f), x), y) -> app(app(f, x), y), app(app(plus(), app(s(), x)), y) -> app(s(), app(app(plus(), x), y)), app(app(plus(), 0()), y) -> y, add() -> app(curry(), plus()) } Weak: {} Interpretation class: deltarestricted [add](delta) = + 1 + 1*delta [curry](delta) = + 0 + 0*delta [s](delta) = + 0 + 0*delta [0](delta) = + 0 + 0*delta [plus](delta) = + 0 + 0*delta [app](delta, X1, X0) = + 1*X0 + 1*X1 + 1 + 0*X0*delta + 1*X1*delta + 0*delta app_tau_1(delta) = delta/(1 + 1 * delta)app_tau_2(delta) = delta/(1 + 0 * delta) Qed