ユニフィケーション
コナー・マクブリッジ(英語版)は、Epigram(英語版)のような依存型(英語版)言語で「ユニフィケーションが利用している構造を表現することにより」、ジョン・アラン・ロビンソンのアルゴリズムを再帰的にすることができ、証明の複数の停止条件は不要になることを示した。
統語論的ユニフィケーションとは別に、意味論的ユニフィケーションも広く使われている。この2つは、項を「等しい」とみなす方法が異なる。統語論的ユニフィケーションでは、置換によって項が構造的に等価になるようにする。意味論的ユニフィケーションでは、2つの項が何らかの理論において合同であるかで判定する。例えば、交換性と結合性において合同な項を「等しい」とするユニフィケーションをAC-ユニフィケーションと呼ぶ。
ユニフィケーションは計算機科学の重要なツールである。特に一階のユニフィケーションは論理プログラミング、プログラミング言語の型システム設計、自動推論などに用いられている。高階ユニフィケーションは定理証明支援で使われている。高階ユニフィケーションに制約を加えたものを実装に採用したプログラミング言語もある。意味論的ユニフィケーションは、背景理論付きSAT (SMT) を解くアルゴリズムや項書き換えアルゴリズムでよく使われている。
一階の項における統語論的ユニフィケーション問題は、同等である可能性のある有限個の式の連言 t 1 = ? u 1 & , ... , & t n = ? u n {\displaystyle t_{1}{\stackrel {?}{=}}u_{1}\And ,\ldots ,\And t_{n}{\stackrel {?}{=}}u_{n}} で表される。この問題を解くには、それぞれの潜在的等式の左辺と右辺が統語論的に等価となるような置換 θ {\displaystyle \theta } を求める必要があり、 t 1 θ = u 1 θ & , ... , & t n θ = u n θ {\displaystyle t_{1}\theta =u_{1}\theta \And ,\ldots ,\And t_{n}\theta =u_{n}\theta } となるようにしなければならない。そのような置換 θ {\displaystyle \theta } を「単一子」(ユニフィケーション作用素)と呼ぶ。ユニフィケーション問題には解がない場合もある。例えば、 x = ?