We are left with following problem, upon which TcT provides the certificate YES(?,POLY). Strict Trs: { f(s(x1), x2, x3, x4, x5) -> f(x1, x2, x3, x4, x5) , f(0(), s(x2), x3, x4, x5) -> f(x2, x2, x3, x4, x5) , f(0(), 0(), s(x3), x4, x5) -> f(x3, x3, x3, x4, x5) , f(0(), 0(), 0(), s(x4), x5) -> f(x4, x4, x4, x4, x5) , f(0(), 0(), 0(), 0(), s(x5)) -> f(x5, x5, x5, x5, x5) , f(0(), 0(), 0(), 0(), 0()) -> 0() } Obligation: innermost runtime complexity Answer: YES(?,POLY) The input was oriented with the instance of 'Polynomial Path Order (PS)' as induced by the safe mapping safe(f) = {}, safe(s) = {1}, safe(0) = {} and precedence empty . Following symbols are considered recursive: {f} The recursion depth is 1. For your convenience, here are the satisfied ordering constraints: f(s(; x1), x2, x3, x4, x5;) > f(x1, x2, x3, x4, x5;) f(0(), s(; x2), x3, x4, x5;) > f(x2, x2, x3, x4, x5;) f(0(), 0(), s(; x3), x4, x5;) > f(x3, x3, x3, x4, x5;) f(0(), 0(), 0(), s(; x4), x5;) > f(x4, x4, x4, x4, x5;) f(0(), 0(), 0(), 0(), s(; x5);) > f(x5, x5, x5, x5, x5;) f(0(), 0(), 0(), 0(), 0();) > 0() Hurray, we answered YES(?,POLY)