11

質問

最も効率的な MGU アルゴリズムは何ですか? その時間複雑度は? スタックオーバーフローの回答で説明するのは簡単ですか?

Google で答えを見つけようとしていますが、ACM サブスクリプションを介してのみアクセスできるプライベート PDF を見つけ続けています。

SICP で 1 つのディスカッションを見つけました: here

「最も一般的な統一アルゴリズム」とは何かについての説明: 「自由変数」と「定数」を含む 2 つの式ツリーを取得します。たとえば、

e1 = (+ x? (* y? 3) 5)
 e2 = (+ z? q? r?)

次に、Most General Unifier アルゴリズムは、2 つの式を同等にする最も一般的なバインドのセットを返します。例えば：

mgu(e1, e2) = { x ↦ z,
                q ↦ (* y 3),
                y ↦ unbound,
                r ↦ 5 }

「最も一般的な」とは、代わりに{x ↦ 1}and {z ↦ 1}and をバインドできることを意味しますが、それはe1and とe2同等になりますが、より具体的になります。

SICP の記事は、それがかなり高価であることを暗示しているようです。

情報については、私が尋ねている理由は、型推論にもこの「統一」アルゴリズムが含まれていることを知っており、それを理解したいからです。

4

2 に答える 2

9

実際に (Prolog などで) 使用されている単純なアルゴリズムは、病的なケースでは指数関数的です。

[Martelli と Montanari][1] による理論的にはより効率的なアルゴリズムがあります (IIRC は線形です) が、実際に発生する単純なケースでははるかに遅いため、あまり使用されません。

[1] http://www.nsl.com/misc/papers/martelli-montanari.pdf

于 2009-05-13T16:03:33.850 に答える
5

Baader と Snyderは、構文上の統一と等式の統一の両方について、いくつかの統一アルゴリズムを発表しました。

彼らは、3 番目の構文統一アルゴリズム (セクション 2.3) が逆アッカーマン関数で実行さO(n×α(n))れるα(n)と述べています。実際の状況では、それは小さな定数に相当します。

于 2011-05-25T11:48:30.897 に答える