Počet záznamů: 1
A Duality Theoretic View on Limits of Finite Structures
- 1.
SYSNO ASEP 0525284 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A Duality Theoretic View on Limits of Finite Structures Tvůrce(i) Gehrke, M. (FR)
Jakl, T. (FR)
Reggio, Luca (UIVT-O) ORCID, SAIZdroj.dok. Foundations of Software Science and Computation Structures. - Cham : Springer, 2020 / Goubault-Larrecq J. ; König B. - ISSN 0302-9743 - ISBN 978-3-030-45230-8 Rozsah stran s. 299-318 Poč.str. 20 s. Forma vydání Tištěná - P Akce FOSSACS 2020: Foundations of Software Science and Computation Structures /23./ Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020 Datum konání 25.04.2020 - 30.04.2020 Místo konání Dublin Země IE - Irsko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. CH - Švýcarsko Klíč. slova Stone duality ; finitely additive measures ; structural limits ; finite model theory ; formal languages ; logic on words Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GA17-04630S GA ČR - Grantová agentura ČR Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000719283800016 EID SCOPUS 85084115569 DOI 10.1007/978-3-030-45231-5_16 Anotace 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 operator”. 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2021
Počet záznamů: 1