YES(?,PRIMREC) We are left with following problem, upon which TcT provides the certificate YES(?,PRIMREC). Strict Trs: { f(g(x)) -> g(g(f(x))) , f(g(x)) -> g(g(g(x))) } Obligation: innermost runtime complexity Answer: YES(?,PRIMREC) The input was oriented with the instance of'multiset path order' as induced by the precedence f > g . Hurray, we answered YES(?,PRIMREC)