一句话：通过 Stone–Priestley 对偶与模型论类型，为有限结构极限建立带概率算子的扩展逻辑及可靠完备演算。
Nesetril 与 Ossona de Mendez 用 Stone pairing 将有限结构嵌入测度空间，从而定义结构极限。本文从对偶理论重新审视该构造：借助 Stone–Priestley 对偶与模型论中的类型概念，通过在一阶逻辑中加入若干“概率算子”来增强表达力，得到一个更精细的有限可加测度空间。作者为扩展逻辑给出可靠且完备的演算，并说明该构造的函子性。结果一方面揭示了结构极限理论的逻辑内核；另一方面表明 Stone pairing 的对偶理论变体对应量词层的添加，从而与字上逻辑的 semiring 量词研究建立联系，而模型论类型是二者的统一概念。该工作沟通了面向语义与面向算法及复杂度的逻辑研究。
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.
@article{paperbot1742,
title = {A duality theoretic view on limits of finite structures: Extended version},
author = {Mai Gehrke and Tomáš Jakl and Luca Reggio},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:16)2022}
}