unifiers

Unifiers are substitutions that make two expressions identical. In logic and computer science, a unifier for two terms is a mapping of variables to terms such that applying the mapping to both terms yields the same result. The most common setting uses first-order terms built from variables, constants, and function symbols. A substitution that achieves this equality is a unifier; among unifiers, a most general unifier or MGU is particularly important because every other unifier can be obtained from it by further substitution of its variables.

Robinson's unification algorithm provides a procedure to compute an MGU if one exists, and to decide whether two terms are unifiable. The algorithm proceeds by repeatedly decomposing function symbols and binding variables to terms while ensuring consistency. An occurs check may be included to prevent binding a variable to a term that already contains that variable, which would create infinite terms; many practical unification implementations omit the occurs check for efficiency, though this can lead to non-finite or inappropriate results in some edge cases.

Unification underpins logic programming languages such as Prolog, where resolution relies on finding MGUs between goals and rules. It also supports type inference in functional languages via Hindley–Milner style type unification, where types are treated as terms and unification determines the most general type. In automated theorem proving and symbolic computation, unification helps reduce problems by recognizing when different representations denote the same structure.

Beyond first-order terms, higher-order unification attempts to unify expressions that include variables that can stand for functions; this area is more complex and not always decidable in general. Unifiers form a set ordered by generality: the MGU is the most general among all unifiers. These concepts are central in term rewriting, logic programming, and type systems, and they continue to be developed in automated reasoning and compiler technology.