YES(?,PRIMREC) We are left with following problem, upon which TcT provides the certificate YES(?,PRIMREC). Strict Trs: { and(tt(), X) -> activate(X) , activate(X) -> X , plus(N, 0()) -> N , plus(N, s(M)) -> s(plus(N, M)) } Obligation: innermost runtime complexity Answer: YES(?,PRIMREC) The input was oriented with the instance of'multiset path order' as induced by the precedence and > s, tt > s, activate > s, plus > s, 0 > s, and ~ tt, and ~ activate, and ~ plus, and ~ 0, tt ~ activate, tt ~ plus, tt ~ 0, activate ~ plus, activate ~ 0, plus ~ 0 . Hurray, we answered YES(?,PRIMREC)