Mai Gehrke ; Tomáš Jakl ; Luca Reggio - A duality theoretic view on limits of finite structures: Extended version

lmcs:6996 - Logical Methods in Computer Science, January 19, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:16)2022
A duality theoretic view on limits of finite structures: Extended versionArticle

Authors: Mai Gehrke ; Tomáš Jakl ; Luca Reggio

    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.


    Volume: Volume 18, Issue 1
    Published on: January 19, 2022
    Accepted on: December 10, 2021
    Submitted on: December 21, 2020
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic
    Funding:
      Source : OpenAIRE Graph
    • Resources and co-resources: a junction between semantics and descriptive complexity; Funder: UK Research and Innovation; Code: EP/T007257/1
    • Duality for Finite Models: Relating Structure and Power; Funder: European Commission; Code: 837724
    • Duality in Formal Languages and Logic - a unifying approach to complexity and semantics; Funder: European Commission; Code: 670624

    Consultation statistics

    This page has been seen 1693 times.
    This article's PDF has been downloaded 632 times.