Termination Proofs in the Dependency Pair Framework May Induce Multiple Recursive Derivational Complexity

Georg Moser & Andreas Schnabl
We study the complexity of rewrite systems shown terminating via the dependency pair framework using processors for reduction pairs, dependency graphs, or the subterm criterion. The complexity of such systems is bounded by a multiple recursive function, provided the complexity induced by the employed base techniques is at most multiple recursive. Moreover this upper bound is tight.