A DUALITY THEORETIC VIEW ON LIMITS OF FINITE STRUCTURES
View / Open Files
Authors
Gehrke, M
Jakl, T
Reggio, L
Publication Date
2022-01-01Journal Title
Logical Methods in Computer Science
ISSN
1860-5974
Publisher
Centre pour la Communication Scientifique Directe (CCSD)
Volume
18
Issue
1
Pages
16:1-16:38
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Gehrke, M., Jakl, T., & Reggio, L. (2022). A DUALITY THEORETIC VIEW ON LIMITS OF FINITE STRUCTURES. Logical Methods in Computer Science, 18 (1), 16:1-16:38. https://doi.org/10.46298/LMCS-18(1:16)2022
Abstract
A systematic theory of structural limits for finite models has been developed by Nešetřil 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.
Sponsorship
EPSRC (EP/T007257/1)
Identifiers
External DOI: https://doi.org/10.46298/LMCS-18(1:16)2022
This record's URL: https://www.repository.cam.ac.uk/handle/1810/334020
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk