scientific article; zbMATH DE number 4016225

From MaRDI portal
Publication:3028368





[For the entire collection see Zbl 0619.00020.] Unifying terms s and t in an equational theory E means finding a substitution \(\sigma\) such that \(\sigma (s)=_ E\sigma (t)\). Unification in the empty theory, i.e., the theory without axioms and so consisting of free terms only, is important for the implementation of programming languages such as Prolog; the general case is of importance for programming languages such as OBJ and for logic programming in general. In this overview, results about the decidability of the question whether given term s and t are unifiable in an equational theory as well as unification algorithms for particular theories of different unification types are presented. Recent methods to construct a unification algorithm for a theory \(E_ 1+E_ 2\) using given unification algorithms for the theories \(E_ 1\) and \(E_ 2\) are discussed. Finally, the complexity of unification is considered. Unification in the empty theory is complete for P and for co-NL; unification is NP-complete for instance in Boolean rings and worse in general.











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 Q3028368)