Automated termination proofs for logic programs by term rewriting
Open Access
- 1 October 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 11 (1) , 1-52
Abstract
There are two kinds of approaches for termination analysis of logic programs: “transformational” and “direct” ones. Direct approaches prove termination directly on the basis of the logic program. Transformational approaches transform a logic program into a Term Rewrite System (TRS) and then analyze termination of the resulting TRS instead. Thus, transformational approaches make all methods previously developed for TRSs available for logic programs as well. However, the applicability of most existing transformations is quite restricted, as they can only be used for certain subclasses of logic programs. (Most of them are restricted to well-moded programs.) In this article we improve these transformations such that they become applicable for any definite logic program. To simulate the behavior of logic programs by TRSs, we slightly modify the notion of rewriting by permitting infinite terms. We show that our transformation results in TRSs which are indeed suitable for automated termination analysis. In contrast to most other methods for termination of logic programs, our technique is also sound for logic programming without occur check , which is typically used in practice. We implemented our approach in the termination prover AProVE and successfully evaluated it on a large collection of examples.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (GI 274/5-2)
This publication has 33 references indexed in Scilit:
- Recurrence with affine level mappings is P-time decidable for CLPTheory and Practice of Logic Programming, 2008
- Nontermination inference of logic programsACM Transactions on Programming Languages and Systems, 2006
- cTI: a constraint-based termination inference tool for ISO-PrologTheory and Practice of Logic Programming, 2005
- On termination of meta-programsTheory and Practice of Logic Programming, 2005
- On proving left termination of constraint logic programsACM Transactions on Computational Logic, 2003
- A semantic basis for the termination analysis of logic programsThe Journal of Logic Programming, 1999
- Sharing is optimalThe Journal of Logic Programming, 1999
- Transformational methodology for proving termination of logic programsThe Journal of Logic Programming, 1998
- Termination of logic programs: the never-ending storyThe Journal of Logic Programming, 1994
- Deriving descriptions of possible values of program variables by means of abstract interpretationThe Journal of Logic Programming, 1992