什么是最佳的"最一般的统一"算法？

Question

这个问题

什么是最有效的闭塞算法？什么是它的时间复杂性？它是简单的，足以描述为一堆溢出答案吗？

我一直试图找到答案在谷歌但继续寻找私人的。Pdf文件，我可以仅仅通过一种含石棉材料的订阅。

我找到一个讨论在sic颗粒: 在这里，

解释什么是"最一般的统一的算法"：采取两种表达的树木包含的"免费变量"和"常数"...例如

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

然后最一般的统一的算法返回的最大组绑定，使两种表达方式等同。

即

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

通过"最一般的"，你可以代替bind(x=1)和(z=1)，还将使e1、e2等，但它将更加具体。

该sic颗粒的文似乎意味着它是合理的昂贵的。

有关信息，其原因我问是因为我知道那种类型的推论也涉及这种"统一"的算法我想了解它。

Answer 1

这是在实践中（例如，在Prolog中）中使用的简单algorith是指数为病理情况下。

有一个理论上更有效的算法由马尔泰利和塔纳（IIRC它是线性的），但它是对于其发生在实践中简单的情况下要慢得多，因此它不大量使用。

Answer 2

巴德尔和Snyder 发表了几篇统一的算法，两个句法统一和等式统一。

他们指出他们的第三个句法统一算法（在第2.3节）运行在O（Nα（n））的，其中α（n）是逆阿克曼函数 - 。在实际情况下这是相当于一个小常数