Equational problems and disunification
Résumé
Roughly speaking, an equational problem is a first order formula whose only predicate symbol is =. We propose some rules for the transformation of equational problems and study their correctness in various models. Then, we give completeness results with respect to some "simple" problems called solved forms. Such completeness results still hold when adding some control which moreover ensures termination. The termination proofs are given for a "weak" control and thus hold for the (large) class of algorithms obtained by restricting the scope of the rules. Finally, it must be noted that a by-product of our method is a decision procedure for the validity in the Herbrand Universe of any first order formula with the only predicate symbol =.