scientific article; zbMATH DE number 3956434
[For the entire collection see Zbl 0587.00019.] The procedure of \textit{D. E. Knuth} and \textit{P. B. Bendix} [Comput. Probl. Abstr. Algebra, Proc. Conf. Oxford 1967, 263-297 (1970; Zbl 0188.049)] completes a system of equations into a confluent one. It proceeds by adding critical pairs when equations superpose themselves in an ambiguous way. \textit{G. Huet} and \textit{J.-M. Hullot} [J. Comput. Syst. Sci. 25, 239- 266 (1982; Zbl 0532.68041)] have shown that for theories with constructors satisfying a so-called principle of definition, the Knuth- Bendix procedure can be used to prove that conjectures are inductive theorems of a given theory (proofs by inductive completion). In this paper, we show that this is the case even when the procedure is restricted in a linear selecting manner: first critical pairs are generated in a linear manner by superposition of one equation of the initial theory into one equation issued from critical pairs (no superposition between two equations both issued from critical pairs); second, for each critical pair, the occurrence of superposition with theory equations is uniquely determined by a selection function. Unlike the Knuth-Bendix procedure, our procedure, when terminating with success, does not produce a confluent system in general. However, the generated system is guaranteed to have the ground-confluence property (confluence for terms without variables). This result suffices to guarantee the conjecture validity. Our restricted completion procedure terminates in many cases where the inductive completion procedure loops, generating infinitely many critical pairs. The procedure applies to theories without constructors [\textit{J. P. Jouannaud} and \textit{E. Kounalis}, Bull. EATCS 27, 49-55 (1985)] and extends to conditional theories and conditional conjectures. It can also incorporate various techniques used in classical induction. The procedure then combines the efficiency of classical induction method with the simplicity of inductive completion.
- Inductive proof search modulo
- Inductive completion with retracts
- Narrowing based procedures for equational disunification
- Extending Bachmair's method for proof by consistency to the final algebra
- A recursion planning analysis of inductive completion
- A strong restriction of the inductive completion procedure
- Automatic proofs by induction in theories without constructors
- Induction = I-axiomatization + first-order consistency.
- Strong forward induction
- scientific article; zbMATH DE number 3891336 (Why is no real title available?)
- scientific article; zbMATH DE number 4090851 (Why is no real title available?)
- scientific article; zbMATH DE number 44069 (Why is no real title available?)
- Completeness and decidability results for first-order clauses with indices
- scientific article; zbMATH DE number 1389652 (Why is no real title available?)
- Inductive proofs by specification transformations
- Rewriting techniques for program synthesis
- On relationship between term rewriting systems and regular tree languages
- Proving equational and inductive theorems by completion and embedding techniques
- Induction using term orderings
- Mechanizable inductive proofs for a class of \(\forall \exists\) formulas
- On the connection between narrowing and proof by consistency
- Inductive theorem proving by consistency for first-order clauses
- Conditional rewriting in focus
- Knuth-bendix completion of horn clause programs for restricted linear resolution and paramodulation
- Proof by consistency in conditional equational theories
- Completion procedures as semidecision procedures
- The strength of sharply bounded induction requires MSP
- Term rewriting induction
- UNICOM: A refined completion based inductive theorem prover
- Higher-order proof by consistency
- Towards a foundation of completion procedures as semidecision procedures
- Testing for the ground (co-)reducibility property in term-rewriting systems
- Automating inductionless induction using test sets
- On ground-confluence of term rewriting systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3725540)