MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { div(x, s(y)) -> d(x, s(y), 0()) , d(x, s(y), z) -> cond(ge(x, z), x, y, z) , cond(true(), x, y, z) -> s(d(x, s(y), plus(s(y), z))) , cond(false(), x, y, z) -> 0() , ge(u, 0()) -> true() , ge(s(u), s(v)) -> ge(u, v) , ge(0(), s(v)) -> false() , plus(n, s(m)) -> s(plus(n, m)) , plus(n, 0()) -> n } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..