Cargando…
A Duality Theoretic View on Limits of Finite Structures
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...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7788618/ http://dx.doi.org/10.1007/978-3-030-45231-5_16 |
_version_ | 1783633065305702400 |
---|---|
author | Gehrke, Mai Jakl, Tomáš Reggio, Luca |
author_facet | Gehrke, Mai Jakl, Tomáš Reggio, Luca |
author_sort | Gehrke, Mai |
collection | PubMed |
description | 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 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. |
format | Online Article Text |
id | pubmed-7788618 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
record_format | MEDLINE/PubMed |
spelling | pubmed-77886182021-01-07 A Duality Theoretic View on Limits of Finite Structures Gehrke, Mai Jakl, Tomáš Reggio, Luca Foundations of Software Science and Computation Structures Article 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 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. 2020-04-17 /pmc/articles/PMC7788618/ http://dx.doi.org/10.1007/978-3-030-45231-5_16 Text en © The Author(s) 2020 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. |
spellingShingle | Article Gehrke, Mai Jakl, Tomáš Reggio, Luca A Duality Theoretic View on Limits of Finite Structures |
title | A Duality Theoretic View on Limits of Finite Structures |
title_full | A Duality Theoretic View on Limits of Finite Structures |
title_fullStr | A Duality Theoretic View on Limits of Finite Structures |
title_full_unstemmed | A Duality Theoretic View on Limits of Finite Structures |
title_short | A Duality Theoretic View on Limits of Finite Structures |
title_sort | duality theoretic view on limits of finite structures |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7788618/ http://dx.doi.org/10.1007/978-3-030-45231-5_16 |
work_keys_str_mv | AT gehrkemai adualitytheoreticviewonlimitsoffinitestructures AT jakltomas adualitytheoreticviewonlimitsoffinitestructures AT reggioluca adualitytheoreticviewonlimitsoffinitestructures AT gehrkemai dualitytheoreticviewonlimitsoffinitestructures AT jakltomas dualitytheoreticviewonlimitsoffinitestructures AT reggioluca dualitytheoreticviewonlimitsoffinitestructures |