No label defined (Q3028368)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4016225
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4016225

      Statements

      0 references
      1987
      0 references
      equational theory
      0 references
      logic programming
      0 references
      unification algorithms
      0 references
      complexity of unification
      0 references
      [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.
      0 references

      Identifiers