Advertisement
Published in:
2005 | OriginalPaper | Chapter
The Dependency Pair Framework: Combining Techniques for Automated Termination Proofs
Authors : Jürgen Giesl, René Thiemann, Peter Schneider-Kamp
Published in: Logic for Programming, Artificial Intelligence, and Reasoning
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The dependency pair approach is one of the most powerful techniques for automated termination proofs of term rewrite systems. Up to now, it was regarded as one of several possible methods to prove termination. In this paper, we show that dependency pairs can instead be used as a general concept to integrate arbitrary techniques for termination analysis. In this way, the benefits of different techniques can be combined and their modularity and power are increased significantly. We[2] refer to this new concept as the “dependency pair
framework
” to distinguish it from the old “dependency pair
approach
”. Moreover, this framework facilitates the development of new methods for termination analysis. To demonstrate this, we present several new techniques within the dependency pair framework which simplify termination problems considerably. We implemented the dependency pair framework in our termination prover
AProVE
and evaluated it on large collections of examples.