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