Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Unification (computer science)
open-in-new
<p>In <a href="/facts/Logic/8JnpJLtt">logic</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, specifically <a href="/facts/Automated_reasoning/x5EdkKoU">automated reasoning</a>, unification is an algorithmic process of <a href="/facts/Solving_equations/2RKaXrDM">solving equations</a> between symbolic <a href="/facts/Expression_(mathematics)/MPrMlYbE">expressions</a>, each of the form <i>Left-hand side = Right-hand side</i>. For example, using <i>x</i>,<i>y</i>,<i>z</i> as variables, and taking <i>f</i> to be an <a href="/facts/Uninterpreted_function/jRlf5LB3">uninterpreted function</a>, the <a href="/facts/Singleton_(mathematics)/LtNVfujT">singleton</a> equation set { <i>f</i>(1,<i>y</i>) = <i>f</i>(<i>x</i>,2) } is a syntactic first-order unification problem that has the substitution { <i>x</i> <a href="/facts/%25E2%2586%25A6/0vJMw0Nm">↦</a> 1, <i>y</i> ↦ 2 } as its only solution. </p><p>Conventions differ on what values variables may assume and which expressions are considered equivalent. In first-order syntactic unification, variables range over <a href="/facts/First-order_terms/M0nXp7dH">first-order terms</a> and equivalence is syntactic. This version of unification has a unique "best" answer and is used in <a href="/facts/Logic_programming/Xgh8lj3F">logic programming</a> and programming language <a href="/facts/Type_system/Tz0bAMS9">type system</a> implementation, especially in <a href="/facts/Hindley%25E2%2580%2593Milner/9GIuBwQ6">Hindley–Milner</a> based <a href="/facts/Type_inference/vX9K8Qhf">type inference</a> algorithms. In higher-order unification, possibly restricted to higher-order pattern unification, terms may include lambda expressions, and equivalence is up to beta-reduction. This version is used in <a href="/facts/Proof_assistant/hjFGxLPn">proof assistants</a> and higher-order logic programming, for example <a href="/facts/Isabelle_(theorem_prover)/CNbtbX83">Isabelle</a>, <a href="/facts/Twelf/s6sIyor7">Twelf</a>, and <a href="/facts/LambdaProlog/dH190mch">lambdaProlog</a>. Finally, in semantic unification or E-unification, equality is subject to background knowledge and variables range over a variety of domains. This version is used in <a href="/facts/SMT_solver/10mBFLFB">SMT solvers</a>, <a href="/facts/Term_rewriting/9PHlnnnJ">term rewriting</a> algorithms, and <a href="/facts/Cryptographic_protocol/0WuyTkFo">cryptographic protocol</a> analysis. </p>