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