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