MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { a__h(X) -> a__g(mark(X), X) , a__h(X) -> h(X) , a__g(X1, X2) -> g(X1, X2) , a__g(a(), X) -> a__f(b(), X) , mark(a()) -> a__a() , mark(b()) -> b() , mark(h(X)) -> a__h(mark(X)) , mark(g(X1, X2)) -> a__g(mark(X1), X2) , mark(f(X1, X2)) -> a__f(mark(X1), X2) , a__f(X, X) -> a__h(a__a()) , a__f(X1, X2) -> f(X1, X2) , a__a() -> a() , a__a() -> b() } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..