论文标题
有限结构限制的二元理论观点：扩展版本
A duality theoretic view on limits of finite structures: Extended version
论文作者
论文摘要
Nesetril和Ossona de Mendez已经开发了有限模型的结构限制的系统理论。它基于这样的见解，即可以通过称为石头配对的地图将有限结构的集合嵌入，并在可以计算所需限制的措施中。我们表明，通过石材 - 普里斯利二元性和模型理论的类型概念而产生的密切相关但更细的（有限添加性）的粒度空间 - 通过通过某些“概率运算符”来丰富一阶逻辑的表达能力。我们为这种扩展的逻辑提供了声音和完整的演算，并揭示了该结构的功能性质。 后果是两个方面。一方面，我们确定了结构限制理论的逻辑要旨。另一方面，我们的构造表明，石材配对的二元性理论变体捕获了添加一层量词，从而与最近在单词上的逻辑上的半级量化器上进行了牢固的联系。在此过程中，我们将类型的模型理论概念确定为此链接背后的统一概念。这些结果有助于桥接计算机科学中逻辑的链接，这些逻辑分别集中在语义上，分别关注与更相关的算法和复杂性领域。
A systematic theory of structural limits for finite models has been developed by Nesetril and Ossona de Mendez. It is based on the insight that the collection of finite structures can be embedded, via a map they call the Stone pairing, in a space of measures, where the desired limits can be computed. We show that a closely related but finer grained space of (finitely additive) measures arises -- via Stone-Priestley duality and the notion of types from model theory -- by enriching the expressive power of first-order logic with certain "probabilistic operators". We provide a sound and complete calculus for this extended logic and expose the functorial nature of this construction. The consequences are two-fold. On the one hand, we identify the logical gist of the theory of structural limits. On the other hand, our construction shows that the duality theoretic variant of the Stone pairing captures the adding of a layer of quantifiers, thus making a strong link to recent work on semiring quantifiers in logic on words. In the process, we identify the model theoretic notion of types as the unifying concept behind this link. These results contribute to bridging the strands of logic in computer science which focus on semantics and on more algorithmic and complexity related areas, respectively.
