MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { gcd(x, 0()) -> x , gcd(0(), y) -> y , gcd(s(x), s(y)) -> if(<(x, y), gcd(s(x), -(y, x)), gcd(-(x, y), s(y))) } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..