scientific article; zbMATH DE number 3956434

From MaRDI portal
Publication:3725540





[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.




Cited in
(34)








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)