YES(?,POLY) 'Pop* (timeout of 60.0 seconds)' -------------------------------- Answer: YES(?,POLY) Input Problem: innermost runtime-complexity with respect to Rules: { and(tt(), X) -> X , plus(N, 0()) -> N , plus(N, s(M)) -> s(plus(N, M)) , x(N, 0()) -> 0() , x(N, s(M)) -> plus(x(N, M), N)} Proof Output: The input was oriented with the instance of POP* as induced by the precedence and > plus, x > plus, and ~ x and safe mapping safe(and) = {}, safe(tt) = {}, safe(plus) = {1}, safe(0) = {}, safe(s) = {1}, safe(x) = {} . For your convenience, here is the input in predicative notation: Rules: { and(tt(), X;) -> X , plus(0(); N) -> N , plus(s(; M); N) -> s(; plus(M; N)) , x(N, 0();) -> 0() , x(N, s(; M);) -> plus(N; x(N, M;))}