高阶统一 [英] Higher-order unification

问题描述

我工作的一个高阶定理证明，其中统一似乎是最困难的子问题。

I'm working on a higher-order theorem prover, of which unification seems to be the most difficult subproblem.

如果休特的算法仍然被认为是国家的最先进的，有没有人要它解释写入到地理解程序员，而不是一个数学家的任何链接？

If Huet's algorithm is still considered state-of-the-art, does anyone have any links to explanations of it that are written to be understood by a programmer rather than a mathematician?

或者在那里它的工作原理和一般的一阶算法，甚至没有任何例子吗？

Or even any examples of where it works and the usual first-order algorithm doesn't?

推荐答案

艺术＆mdash的国家;是的，所以据我所知，所有的算法或多或少地采取同样的形状，休特的（按照逻辑程序设计的理论，虽然我的专长是切）的提供的的，你需要充分高阶匹配：子问题等作为高阶匹配（统一，其中一个任期被关闭），和戴尔·米勒的格局结石，是可判定的。

State of the art — yes, so far as I know all algorithms more or less take the same shape as Huet's (I follow theory of logic programming, although my expertise is tangential) provided you need full higher-order matching: subproblems such as higher-order matching (unification where one term is closed), and Dale Miller's pattern calculus, are decidable.

需要注意的是休特的算法是最好的，在下面的意义和mdash;它像一个半决策算法，即如果它们存在它将会找到unifiers，但它不能保证终止，如果他们不知道。因为我们知道，高阶统一（事实上，第二次统一）是不可判定的，你不能这样做比这更好的。

Note that Huet's algorithm is the best in the following sense — it is like a semi-decision algorithm, in that it will find the unifiers if they exist, but it is not guaranteed to terminate if they do not. Since we know that higher-order unification (indeed, second-order unification) is undecidable, you can't do better than that.

说明：对Conal艾略特的博士论文的前四章，扩展和高阶统一应用应符合法案。这部分重量近80页，具有一定的浓密型的理论，但其良好的动机，是我见过的最可读的帐户。

Explanations: The first four chapters of Conal Elliott's PhD thesis, Extensions and Applications of Higher-Order Unification should fit the bill. That part weighs almost 80 pages, with some dense type theory, but its well motivated, and is the most readable account I've seen.

例如：休特的算法将拿出产品的这个例子：[X（O），Y（SUCC（0））];这必然将困扰的一阶统一算法。

Examples: Huet's algorithm will come up with the goods for this example: [X(o), Y(succ(0))]; which of necessity will perplex a first-order unification algorithm.

这篇关于高阶统一的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！