On the Expressive Power of Sub-Propositional Fragments of Modal Logic
Abstract
Modal logic is a paradigm for several useful and applicable formal systems in computer science. It generally retains the low complexity of classical propositional logic, but notable exceptions exist in the domains of description, temporal, and spatial logic, where the most expressive formalisms have a very high complexity or are even undecidable. In search of computationally well-behaved fragments, clausal forms and other sub-propositional restrictions of temporal and description logics have been recently studied. This renewed interest on sub-propositional logics, which mainly focus on the complexity of the various fragments, raise natural questions on their the relative expressive power, which we try to answer here for the basic multi-modal logic Kn. We consider the Horn and the Krom restrictions, as well as the combined restriction (known as the core fragment) of modal logic, and, orthogonally, the fragments that emerge by disallowing boxes or diamonds from positive literals. We study the problem in a very general setting, to ease transferring our results to other meaningful cases.
Citation
Please, cite this work as:
[BMS16] D. Bresolin, E. Mu~noz-Velasco, and G. Sciavicco. “On the Expressive Power of Sub-Propositional Fragments of Modal Logic”. In: Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016. Ed. by D. Cantone and G. Delzanno. Vol. 226. EPTCS. 2016, pp. 91-104. DOI: 10.4204/EPTCS.226.7. URL: https://doi.org/10.4204/EPTCS.226.7.
Bibliometric data
The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.
Cites
The following graph plots the number of cites received by this work from its publication, on a yearly basis.
Papers citing this work
The following is a non-exhaustive list of papers that cite this work:
[1] J. C. Jung, F. Papacchini, F. Wolter, et al. “Model Comparison Games for Horn Description Logics”. In: 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, Jun. 2019, p. 1–14. DOI: 10.1109/lics.2019.8785658. URL: http://dx.doi.org/10.1109/lics.2019.8785658.