Document Open Access Logo

Comonadic semantics for hybrid logic

Authors Samson Abramsky , Dan Marsden

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.7.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Samson Abramsky
  • University College London, London, UK
Dan Marsden
  • University of Oxford, Oxford, UK

Cite AsGet BibTex

Samson Abramsky and Dan Marsden. Comonadic semantics for hybrid logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.7

Abstract

Hybrid logic is a widely-studied extension of basic modal logic, which corresponds to the bounded fragment of first-order logic. We study it from two novel perspectives: (1) We apply the recently introduced paradigm of comonadic semantics, which provides a new set of tools drawing on ideas from categorical semantics which can be applied to finite model theory, descriptive complexity and combinatorics. (2) We give a novel semantic characterization of hybrid logic in terms of invariance under disjoint extensions, a minimal form of locality. A notable feature of this result is that we give a uniform proof, valid for both the finite and infinite cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Modal and temporal logics
Keywords
  • comonads
  • model comparison games
  • semantic characterizations
  • hybrid logic
  • bounded fragment

Metrics

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

References

  1. 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. IEEE, IEEE, 2017. Google Scholar
  2. Samson Abramsky and Dan Marsden. Comonadic semantics for guarded fragments. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13. IEEE, IEEE, 2021. Google Scholar
  3. Samson Abramsky and Luca Reggio. Aboreal categories: applications to preservation and invariance theorems, 2021. In preparation. Google Scholar
  4. Samson Abramsky and Luca Reggio. Arboreal categories and resources. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 115:1-115:20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  5. Samson Abramsky and Nihil Shah. Relating structure and power: Comonadic semantics for computational resources. Journal of Logic and Computation, 31(6):1390-1428, 2021. Google Scholar
  6. Thorsten Altenkirch, James Chapman, and Tarmo Uustalu. Monads need not be endofunctors. In International Conference on Foundations of Software Science and Computational Structures, pages 297-311. Springer, 2010. Google Scholar
  7. Carlos Areces, Patrick Blackburn, and Maarten Marx. Hybrid logics: Characterization, interpolation and complexity. J. Symb. Log., 66(3):977-1010, 2001. URL: https://doi.org/10.2307/2695090.
  8. Patrick Blackburn. Representation, reasoning, and relational structures: a hybrid logic manifesto. Logic Journal of the IGPL, 8(3):339-365, 2000. Google Scholar
  9. Patrick Blackburn, Maarten De Rijke, and Yde Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2002. Google Scholar
  10. Patrick Blackburn and Klaus Frovin Jørgensen. Reichenbach, Prior and hybrid tense logic. Synthese, 193(11):3677-3689, 2016. Google Scholar
  11. Torben Braüner. Hybrid logic and its proof-theory, volume 37. Springer Science & Business Media, 2010. Google Scholar
  12. Adam Ó Conghaile. Cohomological k-consistency, 2021. Technical Report. Google Scholar
  13. Adam Ó Conghaile and Anuj Dawar. Game comonads and generalised quantifiers. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), pages 16:1-16:17, 2021. URL: http://arxiv.org/abs/2006.16039.
  14. Anuj Dawar, Tomáš Jakl, and Luca Reggio. Lovász-type theorems and game comonads. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470609.
  15. Solomon Feferman. Persistent and invariant formulas for outer extensions. Compositio Mathematica, 20:29-52, 1968. Google Scholar
  16. Solomon Feferman and Georg Kreisel. Persistent and invariant formulas relative to theories of higher order. Bulletin of the American Mathematical Society, 72(3):480-485, 1966. Google Scholar
  17. Erich Grädel. Why are modal logics so robustly decidable? Bull. EATCS, 68:90-103, 1999. Google Scholar
  18. Phokion G. Kolaitis and Moshe Y. Vardi. On the expressive power of datalog: Tools and a case study. In Daniel J. Rosenkrantz and Yehoshua Sagiv, editors, Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA, pages 61-71. ACM Press, 1990. URL: https://doi.org/10.1145/298514.298542.
  19. Azriel Lévy. A hierarchy of formulas in set theory. Number 57 in Memoirs of the American Mathematical Society. American Mathematical Soc., 1965. Google Scholar
  20. Leonid Libkin. Elements of Finite Model Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, 2004. Google Scholar
  21. Ernest G. Manes. Algebraic Theories, volume 26 of Graduate Texts in Mathematics. Springer Science & Business Media, 2012. Google Scholar
  22. Yoàv Montacute and Nihil Shah. The pebble-relation comonad in finite model theory. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.08196.
  23. Jaroslav Nešetřil and Patrice Ossona De Mendez. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022-1041, 2006. Google Scholar
  24. Martin Otto. Elementary proof of the van Benthem-Rosen characterisation theorem. Technical Report 2342, Department of Mathematics, Technische Universität Darmstadt, 2004. Google Scholar
  25. Tom Paine. 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, 352:191-209, 2020. Google Scholar
  26. Eric Rosen. Modal logic over finite structures. Journal of Logic, Language and Information, 6(4):427-439, 1997. Google Scholar
  27. Johan van Benthem. Modal logic and classical logic. Bibliopolis, 1983. Google Scholar
  28. Moshe Y Vardi. Why is modal logic so robustly decidable? Technical Report TR-97-274, Rice University, 1997. Google Scholar
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