Unifikator

Unifikator is a term used in logic, type theory, and computer science to denote a component or algorithm that computes unifications between symbolic expressions. Its primary goal is to find a substitution that makes a set of terms identical, or determine that no such substitution exists. When successful, the output is typically the most general unifier, a substitution that allows all equations to be satisfied without introducing unnecessary constraints.

Inputs to a unifikator are usually equations between terms built from variables, constants, and function symbols. A correct unifikator may perform an occurs check to prevent infinite substitutions, ensuring that a variable is not equated with a term containing that variable. If a unification problem is solvable, the unifikator returns an MGU; otherwise it reports failure.

Several algorithms implement the unification task. Robinson’s unification algorithm laid the foundation for first-order unification. The Martelli–Montanari algorithm is another widely used approach, often favored for its simplicity and efficiency in practice. Real-world implementations may differ in whether they include the occurs check, how they handle backtracking, or whether they support extensions such as equational theories or higher-order terms.

Applications of a unifikator are broad. In logic programming, it underpins the matching and variable binding of terms. In type systems, it supports type inference and type checking. In automated theorem proving and symbolic computation, unification helps simplify equations and derive substitutions. Variants exist to handle specialized theories, such as associative-commutative function symbols or higher-order unification.

See also: unification, most general unifier, Robinson’s unification algorithm, Martelli–Montanari unification, Prolog, type inference.