Comonadic semantics for hybrid logic

Marsden, Dan; Abramsky, Samson

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.

Citation

Marsden, D., & Abramsky, S. (2022, August). Comonadic semantics for hybrid logic. Presented at 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria

• Presentation Conference Type: Edited Proceedings
• Conference Name: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
• Start Date: Aug 22, 2022
• End Date: Aug 26, 2022
• Acceptance Date: Jun 21, 2022
• Online Publication Date: Aug 22, 2022
• Publication Date: Aug 22, 2022
• Deposit Date: Oct 10, 2024
• Publicly Available Date: Dec 17, 2024
• Peer Reviewed: Peer Reviewed
• Pages: 7:1-7:14
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series Number: 241
• Series ISSN: 1868-8969
• Book Title: Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
• ISBN: 9783959772563
• DOI: https://doi.org/10.4230/LIPIcs.MFCS.2022.7
• Public URL: https://nottingham-repository.worktribe.com/output/40561288
• Publisher URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.7