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
1987
0 references
equational theory
0 references
logic programming
0 references
unification algorithms
0 references
complexity of unification
0 references
0.8927744
0 references
0.8774142
0 references
0 references
0.8507594
0 references
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