Abramsky, S;
Marsden, D;
(2022)
Comonadic semantics for hybrid logic.
In:
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022).
(pp. 7.1-7.14).
Schloss Dagstuhl – Leibniz-Zentrum für Informatik: Dagstuhl, Germany.
Preview |
PDF
LIPIcs-MFCS-2022-7.pdf - Published Version Download (729kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | Comonadic semantics for hybrid logic |
| Event: | 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) |
| ISBN-13: | 9783959772563 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.MFCS.2022.7 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.MFCS.2022.7 |
| Language: | English |
| Additional information: | © Samson Abramsky and Dan Marsden; licensed under Creative Commons License CC-BY 4.0 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). |
| Keywords: | comonads, model comparison games, semantic characterizations, hybrid logic, bounded fragment |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10155965 |
Archive Staff Only
 |
View Item |
