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