什么是最佳的"最一般的统一"算法?
-
21-08-2019 - |
题
这个问题
什么是最有效的闭塞算法?什么是它的时间复杂性?它是简单的,足以描述为一堆溢出答案吗?
我一直试图找到答案在谷歌但继续寻找私人的。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颗粒的文似乎意味着它是合理的昂贵的。
有关信息,其原因我问是因为我知道那种类型的推论也涉及这种"统一"的算法我想了解它。
解决方案
这是在实践中(例如,在Prolog中)中使用的简单algorith是指数为病理情况下。
有一个理论上更有效的算法由马尔泰利和塔纳(IIRC它是线性的),但它是对于其发生在实践中简单的情况下要慢得多,因此它不大量使用。
其他提示
巴德尔和Snyder 发表了几篇统一的算法,两个句法统一和等式统一。
他们指出他们的第三个句法统一算法(在第2.3节)运行在O(Nα(n))的,其中α(n)是逆阿克曼函数 - 。在实际情况下这是相当于一个小常数
不隶属于 StackOverflow