Termination proofs for logic programs
The volume is broadly conceived (in the good sense) and it can serve as a thorough introduction to the termination problem of logic programs and generally as a summary of the latest important results in the area of logic programming. A technique for the automatic generation of termination proofs for logic programs is presented. Such a technique cannot be complete due to the undecidability of the halting problem for Turing machines. A reasonable goal is achieved - to identify sufficient criteria for termination which are of practical interest. Pure Prolog programs are investigated, the nonlogical features of Prolog still deserve serious analysis. Since the only potential source of infinite computations in pure Prolog (without side effects) is recursion, the problem of automatic termination proofs is tractable. A termination proof gives evidence of the fact that the recursive instance of a problem is easier to solve than the original problem. The technique is based on comparison of tuples of terms and proving that the terms occurring in recursive calls become smaller according to a well founded ordering. The occurrence of local variables poses difficulties which are overcome by semantic approach. An algorithm deriving linear inequalities for predicates is applied. It assumes that the program is normalized and has no mutual recursion (which is eliminated by static program transformation). Compared with the approach taken by Ullman and van Gelder, the author presents a more general approach in the format of inequalities and in the way how sizes of terms are measured. This more powerful method can handle quicksort and permutation where the technique of Ullman and van Gelder does not suffice. However, the mergesort remains beyond the scope.
- Automated termination proofs for logic programs by term rewriting
- scientific article; zbMATH DE number 879005
- Reasoning about termination of pure Prolog programs
- A general framework for automatic termination analysis od logic programs
- Automated Termination Analysis for Logic Programs by Term Rewriting
- A general criterion for avoiding infinite unfolding during partial deduction
- Reasoning about termination of pure Prolog programs
- Norms on terms and their use in proving universal termination of a logic program
- Deriving fold/unfold transformations of logic programs using extended OLDT-based abstract interpretation
- On proving the termination of algorithms by machine
- A logical semantics for depth-first Prolog with ground negation
- A framework for incremental learning of logic programs
- Some classes of Prolog programs inferable from positive data
- Automated termination proofs for logic programs by term rewriting
- Inference of Termination Conditions for Numerical Loops in Prolog
- scientific article; zbMATH DE number 4176501 (Why is no real title available?)
- Termination prediction for general logic programs
- scientific article; zbMATH DE number 4072437 (Why is no real title available?)
- Transformational methodology for proving termination of logic programs
- Strong termination of logic programs
- Termination of logic programs: the never-ending story
- scientific article; zbMATH DE number 1149425 (Why is no real title available?)
- Detecting optimal termination conditions of logic programs
- On modular termination proofs of general logic programs
- scientific article; zbMATH DE number 1497822 (Why is no real title available?)
- Termination and reduction checking for higher-order logic programs
- Termination of constraint logic programs
- scientific article; zbMATH DE number 773980 (Why is no real title available?)
- scientific article; zbMATH DE number 879005 (Why is no real title available?)
- Termination analysis for partial functions
- Proving termination of general Prolog programs
- Terminating sequent calculi for proving and refuting formulas in S4
- Localized operational termination in general logics
- Reasoning in Dynamic Logic about Program Termination
- Input-Termination of Logic Programs
- Termination Analysis of Logic Programs Based on Dependency Graphs
- On the inference of natural level mappings
- Proving termination for logic programs by the query-mapping pairs approach
- Proving termination with adornments
- scientific article; zbMATH DE number 6606377 (Why is no real title available?)
- -Universal termination of logic programs
- Termination of logic programs: Transformational methods revisited
- A general framework for automatic termination analysis od logic programs
- Proving mutual termination
- Verifying termination and reduction properties about higher-order logic programs
This page was built for publication: Termination proofs for logic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1188722)