Počet záznamů: 1
A categorical account of composition methods in logic
- 1.
SYSNO ASEP 0579478 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A categorical account of composition methods in logic Tvůrce(i) Jakl, Tomáš (MU-W) SAI, ORCID
Marsden, D. (GB)
Shah, N. (GB)Zdroj.dok. 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) Proceedings. - New York : IEEE, 2023 - ISBN 979-8-3503-3588-0 Rozsah stran s. 1-14 Poč.str. 14 s. Forma vydání Tištěná - P Akce LICS 2023: Annual ACM/IEEE Symposium on Logic in Computer Science /38./ Datum konání 26.06.2023 - 29.06.2023 Místo konání Boston Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova computer circuits ; equivalence classes ; finite model theory Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Institucionální podpora MU-W - RVO:67985840 UT WOS 001036707700034 EID SCOPUS 85166002522 DOI 10.1109/LICS56636.2023.10175751 Anotace We present a categorical theory of the composition methods in finite model theory - a key technique enabling modular reasoning about complex structures by building them out of simpler components. The crucial results required by the composition methods are Feferman-Vaught-Mostowski (FVM) type theorems, which characterize how logical equivalence be-haves under composition and transformation of models.Our results are developed by extending the recently introduced game comonad semantics for model comparison games. This level of abstraction allow us to give conditions yielding FVM type results in a uniform way. Our theorems are parametric in the classes of models, logics and operations involved. Furthermore, they naturally account for the positive existential fragment, and extensions with counting quantifiers of these logics. We also reveal surprising connections between FVM type theorems, and classical concepts in the theory of monads.We illustrate our methods by recovering many classical theorems of practical interest, including a refinement of a previous result by Dawar, Severini, and Zapata concerning the 3-variable counting logic and cospectrality. To highlight the importance of our techniques being parametric in the logic of interest, we prove a family of FVM theorems for products of structures, uniformly in the logic in question, which cannot be done using specific game arguments. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2024 Elektronická adresa https://doi.org/10.1109/LICS56636.2023.10175751
Počet záznamů: 1