Document Open Access Logo

Game Comonads & Generalised Quantifiers

Authors Adam Ó Conghaile , Anuj Dawar

PDF
Thumbnail PDF

File

LIPIcs.CSL.2021.16.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Adam Ó Conghaile
  • Department of Computer Science and Technology, University of Cambridge, UK
Anuj Dawar
  • Department of Computer Science and Technology, University of Cambridge, UK

Funding

Research funded in part by EPSRC grant EP/T007257/1.

Cite AsGet BibTex

Adam Ó Conghaile and Anuj Dawar. Game Comonads & Generalised Quantifiers. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CSL.2021.16

Abstract

Game comonads, introduced by Abramsky, Dawar and Wang and developed by Abramsky and Shah, give an interesting categorical semantics to some Spoiler-Duplicator games that are common in finite model theory. In particular they expose connections between one-sided and two-sided games, and parameters such as treewidth and treedepth and corresponding notions of decomposition. In the present paper, we expand the realm of game comonads to logics with generalised quantifiers. In particular, we introduce a comonad graded by two parameter n ≤ k such that isomorphisms in the resulting Kleisli category are exactly Duplicator winning strategies in Hella’s n-bijection game with k pebbles. We define a one-sided version of this game which allows us to provide a categorical semantics for a number of logics with generalised quantifiers. We also give a novel notion of tree decomposition that emerges from the construction.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Theory of computation → Abstraction
Keywords
  • Logic
  • Finite Model Theory
  • Game Comonads
  • Generalised Quantifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata. The Quantum Monad on Relational Structures. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of LIPIcs, pages 35:1-35:19, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.35.
  2. Samson Abramsky, Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield. A comonadic view of simulation and quantum resources. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2019. URL: https://doi.org/10.1109/LICS.2019.8785677.
  3. Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12, June 2017. URL: https://doi.org/10.1109/LICS.2017.8005129.
  4. Samson Abramsky and Nihil Shah. 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, volume 119 of LIPIcs, pages 2:1-2:17, 2018. URL: https://doi.org/10.4230/LIPIcs.CSL.2018.2.
  5. Anuj Dawar. Generalized Quantifiers and Logical Reducibilities. Journal of Logic and Computation, 5(2):213-226, 1995. URL: https://doi.org/10.1093/logcom/5.2.213.
  6. Anuj Dawar, Erich Grädel, and Wied Pakusa. Approximations of isomorphism and logics with linear-algebraic operators. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 112:1-112:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.112.
  7. Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner. Logics with rank operators. In Proceedings of the 2009 24th Annual IEEE Symposium on Logic In Computer Science, LICS '09, pages 113-122, Washington, DC, USA, 2009. IEEE Computer Society. URL: https://doi.org/10.1109/LICS.2009.24.
  8. Anuj Dawar and Lauri Hella. The expressive power of finitely many generalized quantifiers. Information and Computation, 123(2):172-184, 1995. Google Scholar
  9. Anuj Dawar and Bjarki Holm. Pebble games with algebraic rules. Fundamenta Informaticae, Vol. 150, nr 3/4:281-316, 2017. Google Scholar
  10. Anuj Dawar, Steven Lindell, and Scott Weinstein. Infinitary logic and inductive definability over finite structures. Information and Computation, 119(2):160-175, 1995. Google Scholar
  11. Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Springer, 2nd edition, 1999. Google Scholar
  12. Erich Grädel and Wied Pakusa. Rank logic is dead, long live rank logic! The Journal of Symbolic Logic, 84(1):54–87, 2019. URL: https://doi.org/10.1017/jsl.2018.33.
  13. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  14. Jevgeni Haigora and Kerkko Luosto. On logics extended with embedding-closed quantifiers, 2014. URL: http://arxiv.org/abs/1401.6682.
  15. Lauri Hella. Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic, 43(3):235-271, 1989. URL: https://doi.org/10.1016/0168-0072(89)90070-5.
  16. Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. URL: https://doi.org/10.1006/inco.1996.0070.
  17. Phokion G. Kolaitis and Jouko A. Väänänen. Generalized quantifiers and pebble games on finite structures. Annals of Pure and Applied Logic, 74(1):23-75, 1995. URL: https://doi.org/10.1016/0168-0072(94)00025-X.
  18. Phokion G. Kolaitis and Moshe Y. Vardi. Infinitary logic for computer science. In Automata, Languages and Programming, pages 450-473, 1992. Google Scholar
  19. Phokion G. Kolaitis and Moshe Y. Vardi. A game-theoretic approach to constraint satisfaction. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, pages 175-181, 2000. Google Scholar
  20. Leonid Libkin. Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series). SpringerVerlag, 2004. Google Scholar
  21. Per Lindström. First order predicate logic with generalized quantifiers. Theoria, 32(3):186-195, 1966. URL: https://doi.org/10.1111/j.1755-2567.1966.tb00600.x.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact