晶格是用什么？

Question

维基百科 说:

完整的晶格出现在数学和计算机科学的许多应用中

它只是指计算中使用的标准布尔代数是一个完整的晶格吗？在晶格的抽象级别而不是专门使用布尔逻辑的抽象级别上工作，我们是否会获得什么？

Google搜索并没有发现很多关于该主题的信息，但是我可能使用了错误的关键字。

Answer 1

例如，请参阅本书： 晶格理论带有应用，Vijay K. Garg, ，从如下开始：

现在，部分秩序和晶格理论在计算机科学和工程学的许多学科中都起着重要作用。例如，它们在分布式计算（向量时钟，全局谓词检测），并发理论（Pomset，出现网络），编程语言语义（定点语义）和数据挖掘（概念分析）中具有应用。它们在其他数学学科中也很有用，例如组合学，数理论和群体理论。在本书中，我以部分顺序理论以及它们在计算机科学中的应用中介绍了重要的结果。本书的偏见是关于晶格理论（算法）和应用（尤其是分布式系统）的计算方面的偏见。

这本书似乎没有提及递归理论（可计算集的理论），而是从维基百科的文章中 计算理论, ， 我们看：

当Post将简单集的概念定义为具有无限含量集合的无限补体的RE集合时，他开始研究递归枚举的集合的结构。这个晶格成为了一个充分的结构。递归集可以在此结构中通过基本结果来定义，即在且仅当集合及其补体都递归枚举时，集合是递归的。无限的RE集始终具有无限的递归子集；但是另一方面，存在简单的集合，但没有共同递归超集。 POST（1944）引入了已经过度精打细算和超级气味套装。后来构建了最大集合，这是RE集合，使每个RE Superset都是给定最大设置的有限变体，或者是共限定的。 Post在研究该晶格中的最初动机是找到一个结构概念，使得满足该特性的每个集合既不是递归集的Turing程度，也不是停止问题的图灵程度。邮政没有找到这样的属性，也没有解决他的问题的解决方案。 Harrington and Soare（1991）最终发现了这样的财产。

进一步阅读，请参阅博客文章 程序员和非计算机科学家的晶格理论.

Answer 2

PålGD给出的参考确实非常适合。因此，让我们专注于这个答案中的小问题。不久前，我已经对晶格进行了一些阅读，并开始怀疑半静脉曲张的概念是否不适合应用程序。您可能会反对一个完整的半晶格也是一个晶格，但是同构和子结构（即sublattices和subsemilattices）是不同的。

在研究半群时，我首先遇到（半）晶格，作为交换性的半群。然后，我考虑了层次结构和晶格之间的关系，并注意到一棵树自然也是半层次。然后，我在安全环境和程序分析中找到了晶格，在我看来，半层次结构是非常重要的部分，而晶格只是因为它可以“免费”而获得晶格。即使对于Heyting代数，连词和分离之间也存在不对称性，这向我表明，不对称的半层次模型可能比对称晶格模型更多地提供洞察力。

Answer 3

一个非常重要但不是那么著名的案例 - 在理论家中众所周知，但在被教导要在本科生的意义上不太熟知 - 使用格子是为了证明 单调电路计算集团大小的超多个单位下限 为此 拉兹博罗夫 赢了 Nevanlinna奖. 。但是，原始结构非常技术性，后来的构造例如 Berg/Ulfberg 简化框架，而无需引用晶格。

因此，在这种情况下，晶格理论被用作发现原始证明的框架，但后来的配方倾向于直接将其作为概念简化。

因此，是的是，晶格可以被视为一个更异国情调的数学对象[Razborov在其他地方谈到了他将高级数学应用于CS的风格]，这可能与CS中其他一些其他更“混凝土”对象相对应，在这种情况下，它是“近似门”。即在电路中给出“近似正确”答案的布尔门，并且晶格是一种“感应结构”，用于在精确电路之间转换为不精确的，近似电路。

Answer 4

从那以后我找到了免费纸 订购的集合和完整的晶格：计算机科学的底漆, ，对于其他感兴趣的读者。

Answer 5

常规边缘标签和相关结构形成分布晶格（例如，请参见 这里）。可以利用这是通过所有常规边缘标签的空间进行有效搜索的（请参阅 这里）。作为应用程序，您可以确定是否可以绘制地图为 摄影 面孔的特定区域分配。

Answer 6

另外，令人惊讶的是（至少对我来说） 密码学. 。检查一下，它允许对已知的密码系统进行新的攻击，并希望对量词后计算的加密系统产生希望。