Constructing Decision Procedures in Equational Clausal Logic

Article type: Research Article

Authors: Peltier, Nicolas

Affiliations: LEIBNIZ-IMAG, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France

Abstract: A method is proposed to construct decision procedures for various subclasses of first-order logic with equality. We define a notion of complexity of first-order terms and equations, and we propose semantic and syntactic criteria ensuring that existing refinements of the paramodulation calculus terminate on the considered clause sets. These refinements use reduction orderings, selection functions and simplification rules. Since they are sound and refutationally complete, the corresponding classes of formulae are decidable. Moreover, the automatic extraction of models from saturated clause sets is also possible. A discussion and detailed comparisons with existing works in the field are provided, together with numerous examples and some undecidability results.

Journal: Fundamenta Informaticae, vol. 54, no. 1, pp. 17-65, 2003