Abstract. In this work, we extend the dependency pair approach for automated proofs of termination in order to prove the termination of narrowing. Our extension of the dependency pair approach generalizes the standard notion of dependency pairs by taking specifically into account the dependencies between the left-hand side of a rewrite rule and its own argument subterms. We demonstrate that the new narrowing dependency pairs exactly capture the narrowing termination behavior and provide an effective termination criterion which we prove to be sound and complete. Finally, we discuss how the problem of analyzing narrowing chains can be recast as a standard analysis problem for traditional (rewriting) chains, so that the proposed technique can be effectively mechanized by reusing the standard DP infrastructure.
Alpuente, Escobar and Iborra extended the dependency pair framework to proving the termination of narrowing for arbitrary TRSs REF , adding pairs for echoing of narrowing into the dependency pairs.
Termination of Narrowing Using Dependency Pairs
In Proc. of the 24th Int’l Conf. on Logic Programming (ICLP 2008
Computer Science