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