Structure and power : an emerging landscape

• Autorzy: Abramsky Samson

Identyfikatory

DOI

10.3233/FI-222116

• Języki publikacji: EN

Abstrakty

EN

In this paper, we give an overview of some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics. The motivations for this work come from Computer Science, but there may also be something of interest for model theorists and other logicians. The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings. One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way: the Ehrenfeucht-Fraisse~game; the quantifier rank fragments of first-order logic; the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction of this fragment to the existential positive part, and (iii) the extension with counting quantifiers; and the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez). Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth. Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters. This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers. Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages. Examples include semantic characterisation and preservation theorems, and Lovasz-type results on counting homomorphisms.

Słowa kluczowe

EN

emerging landscape

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 186, nr 1-4
• Strony: 1--26
• Opis fizyczny: Bibliogr. 35 poz., tab.

Twórcy

autor

Abramsky Samson

• Department of Computer Science University College London

Bibliografia

• [1] Abramsky S, and Reggio L. Arboreal categories: An axiomatic theory of resources. Preprint available at https://arxiv.org/abs/2102.08109, 2022.
• [2] Abramsky S, and Reggio L. Arboreal Categories and Preservation Theorems. Preprint, 2022.
• [3] Abramsky S. Whither semantics? Theoretical Computer Science, 2020. 807:3-14. doi:10.48550/arXiv.2010.13328.
• [4] Abramsky S. Notes on cohomological width and presheaf representations, 2022. Technical Report.
• [5] Abramsky S, Barbosa RS, Kishida K, Lal R, and Mansfield S. Contextuality, cohomology and paradox. In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic, CSL 2015,
• [6] Abramsky S. and Brandenburger A. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics, 2011. 13(11):113036. doi:10.1088/1367-2630/13/11/113036.
• [7] Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Logic in Computer Science (LICS), 2017 32nd Annual ACM/IEEE Symposium on, IEEE, 2017 pages 1-12. doi:10.48550/arXiv.1704.05124.
• [8] Abramsky S, Jakl T, and Paine T. Discrete density comonads and graph parameters. Submitted, 2022. doi:10.48550/arXiv.2205.06589.
• [9] Abramsky S, and Marsden D. Comonadic semantics for guarded fragments. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2021 pages 1-13. doi:10.1109/LICS52264.2021.9470594.
• [10] Abramsky S, and Marsden D. Comonadic semantics for hybrid logic and bounded fragments. 2021. arXiv preprint arXiv:2110.09844.
• [11] Abramsky S, and Reggio L. Arboreal categories and resources. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.115.
• [12] Abramsky S, and Shah N. Relating structure and power: Comonadic semantics for computational resources. In 27th EACSL Annual Conference on Computer Science Logic, CSL 2018, September 4-7, 2018, Birmingham, UK, 2018 pages 2:1-2:17. doi:10.1007/978-3-030-00389-0 1.
• [13] Abramsky S, and Shah N. Relating structure and power: Comonadic semantics for computational resources. Journal of Logic and Computation, 2021. 31(6):1390-1428. doi:10.1093/logcom/exab048.
• [14] Beke T, and Rosický J. Abstract elementary classes and accessible categories. Annals of Pure and Applied Logic, 2012. 163(12):2008-2017. doi:10.1016/j.apal.2012.06.003.
• [15] Blackburn P, de Rijke M, and Venema Y. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2002. ISBN-13:978-1881526964, 10:9781881526964.
• [16] Conghaile A O’. Cohomological k-consistency, 2022. Technical Report.
• [17] Conghaile A ´O, and Dawar A. Game comonads and generalised quantifiers. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), 2021 pages 16:1-16:17. doi:10.48550/arXiv.2006.16039.
• [18] Dawar A, Jakl T, and Reggio L. Lov´asz-type theorems and game comonads. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021 pages 1-13. doi:10.1109/LICS52264.2021.9470609.
• [19] de Rijke M. A note on graded modal logic. Studia Logica, 2000. 64(2):271-283. doi:10.1023/A:1005245900406.
• [20] Ebbinghaus HD, and Flum J. Finite model theory. Springer Science & Business Media, 2005.
• [21] Ehrenfeucht A. An application of games to the completeness problem for formalized theories. Fund. Math, 1961. 49(2):129-141. ISSN-0016-2736.
• [22] Fra¨ıss´e R. Sur quelques classifications des syst`emes de relations. In Publications Scientifiques, S´erie A, Universit´e d’Alger 1954 pages 35-182.
• [23] Gr¨adel E. Why are modal logics so robustly decidable? Bull. EATCS, 1999. 68:90-103.
• [24] Hodges W. A shorter model theory. Cambridge university press, 1997. ISBN-9780521587136.
• [25] Jakl T, Marsden D, and Shah N. A game comonadic account of courcelle and feferman-vaught-mostowski theorems. 2022. arXiv preprint arXiv:2205.05387.
• [26] Joyal A, Nielson M, and Winskel G. Bisimulation and open maps. In [1993] Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science, IEEE 1993 pages 418-427. doi:10.1109/LICS.1993.287566.
• [27] Lovasz L. Operations with structures. Acta Math. Acad. Sci. Hungar., 1967. 18:321-328. doi:10.1007/BF02280291.
• [28] Lane SM. Categories for the working mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 2013. doi:10.1007/978-1-4757-4721-8.
• [29] Montacute Y, and Shah N. The pebble-relation comonad in finite model theory. 2021. arXiv preprint arXiv:2110.08196.
• [30] Neˇsetˇril J, and De Mendez PO. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 2006. 27(6):1022-1041. doi:10.1016/j.ejc.2005.01.010.
• [31] Otto M. Bisimulation invariance and finite models. In Logic Colloquium ’02, volume 27 of Lect. Notes Log., Assoc. Symbol. Logic, La Jolla, CA, 2006 pages 276-298. doi:10.1017/9781316755723.013.
• [32] Paine T. A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem. Electronic Notes in Theoretical Computer Science, 2020. 352:191-209. doi:10.1016/j.entcs.2020.09.010.
• [33] Reggio L. Polyadic sets and homomorphism counting. 2021. arXiv preprint arXiv:2110.11061v3.
• [34] Rossman B. Homomorphism Preservation Theorems. JACM, 2008. 55(3):15.
• [35] Vardi MY. Why is modal logic so robustly decidable? Technical Report TR-97-274, Rice University, 1997. URL https://hdl.handle.net/1911/96465.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)