scientific article; zbMATH DE number 4016225
[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.
- scientific article; zbMATH DE number 4053011
- Unification: a multidisciplinary survey
- Unification: not just a thing of beauty
- scientific article; zbMATH DE number 2232298
- Generalizations of unification
- Introduction to the special issue: Unification
- A model of comprehensive unification
- scientific article; zbMATH DE number 3871321
- scientific article; zbMATH DE number 3936507
- scientific article; zbMATH DE number 4155934
- The transition to unigroups
- Relaxed unification -- proposal
- Essential unifiers
- Source-tracking unification
- Syntactic unification as a geometric operation in free modules over certain rings
- On the complexity of Boolean unification
- A strict border for the decidability of E-unification for recursive functions
- Complexity of linear standard theories
- scientific article; zbMATH DE number 3871321 (Why is no real title available?)
- scientific article; zbMATH DE number 3936507 (Why is no real title available?)
- scientific article; zbMATH DE number 3957052 (Why is no real title available?)
- scientific article; zbMATH DE number 4043301 (Why is no real title available?)
- scientific article; zbMATH DE number 4047179 (Why is no real title available?)
- Unification in incompletely specified theories: A case study
- scientific article; zbMATH DE number 1267560 (Why is no real title available?)
- Unification with sequence variables and flexible arity symbols and its extension with pattern-terms
- Uniting Observers
- Uninorm Basics
- scientific article; zbMATH DE number 2232298 (Why is no real title available?)
- Schematic saturation for decision and unification problems.
- Source-tracking unification.
- Unification theory
- Some results on equational unification
- Exceptional unification of families and forces
- Unification in commutative rings is not finitary
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)