Robinson unification algorithm

E911972

The Robinson unification algorithm is the foundational procedure in automated theorem proving that computes the most general unifier of logical expressions, forming the basis of first-order logic resolution methods.

All labels observed (1)

Label Occurrences
Robinson unification algorithm canonical 1

How this entity was disambiguated

Statements (47)

Predicate Object
instanceOf algorithm in logic ⓘ
procedure in automated theorem proving ⓘ
unification algorithm ⓘ
assumes first-order terms built from variables, function symbols, and constants ⓘ
basedOn substitution in first-order logic ⓘ
term rewriting ⓘ
complexity runs in time roughly linear in term size with appropriate data structures ⓘ
coreConcept most general unifier ⓘ
occurs check ⓘ
substitution set ⓘ
term matching ⓘ
failsWhen function symbols at same position differ ⓘ
occurs check detects cyclic substitution ⓘ
field artificial intelligence ⓘ
automated theorem proving ⓘ
first-order logic ⓘ
mathematical logic ⓘ
formalizes unification problem for first-order terms ⓘ
influenced automated deduction systems ⓘ
design of logic programming languages ⓘ
input pair of first-order terms ⓘ
set of equations between terms ⓘ
introducedBy John Alan Robinson ⓘ
introducedIn 1960s ⓘ
introducedInContextOf resolution principle ⓘ
namedAfter John Alan Robinson ⓘ
output failure if terms are not unifiable ⓘ
most general unifier ⓘ
property complete for unification of first-order terms ⓘ
computes most general unifier if it exists ⓘ
sound ⓘ
purpose compute most general unifier ⓘ
support resolution-based theorem proving ⓘ
unify logical expressions ⓘ
relatedTo Herbrand universe ⓘ
SLD-resolution ⓘ
resolution refutation ⓘ
step apply substitution to remaining equations ⓘ
orient equation to substitute variable by term ⓘ
repeat until no equations remain or conflict arises ⓘ
select unsolved equation between terms ⓘ
usedIn Prolog implementations ⓘ
constraint logic programming ⓘ
logic programming ⓘ
resolution theorem proving ⓘ
term rewriting systems ⓘ
type inference systems ⓘ

How these facts were elicited

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Huet unification algorithm → relatedTo → Robinson unification algorithm ⓘ