On the decidability of elementary modal logics

J. Michaliszyn, J. Otop, E. Kieroňski, ACM Transactions on Computational Logic 17 (2015).

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
; ;
Department
Abstract
We consider the satisfiability problem for modal logic over first-order definable classes of frames.We confirm the conjecture from Hemaspaandra and Schnoor [2008] that modal logic is decidable over classes definable by universal Horn formulae. We provide a full classification of Horn formulae with respect to the complexity of the corresponding satisfiability problem. It turns out, that except for the trivial case of inconsistent formulae, local satisfiability is eitherNP-complete or PSPACE-complete, and global satisfiability is NP-complete, PSPACE-complete, or ExpTime-complete. We also show that the finite satisfiability problem for modal logic over Horn definable classes of frames is decidable. On the negative side, we show undecidability of two related problems. First, we exhibit a simple universal three-variable formula defining the class of frames over which modal logic is undecidable. Second, we consider the satisfiability problem of bimodal logic over Horn definable classes of frames, and also present a formula leading to undecidability.
Publishing Year
Date Published
2015-09-01
Journal Title
ACM Transactions on Computational Logic
Volume
17
Issue
1
Article Number
2
IST-REx-ID

Cite this

Michaliszyn J, Otop J, Kieroňski E. On the decidability of elementary modal logics. ACM Transactions on Computational Logic. 2015;17(1). doi:10.1145/2817825
Michaliszyn, J., Otop, J., & Kieroňski, E. (2015). On the decidability of elementary modal logics. ACM Transactions on Computational Logic, 17(1). https://doi.org/10.1145/2817825
Michaliszyn, Jakub, Jan Otop, and Emanuel Kieroňski. “On the Decidability of Elementary Modal Logics.” ACM Transactions on Computational Logic 17, no. 1 (2015). https://doi.org/10.1145/2817825.
J. Michaliszyn, J. Otop, and E. Kieroňski, “On the decidability of elementary modal logics,” ACM Transactions on Computational Logic, vol. 17, no. 1, 2015.
Michaliszyn J, Otop J, Kieroňski E. 2015. On the decidability of elementary modal logics. ACM Transactions on Computational Logic. 17(1).
Michaliszyn, Jakub, et al. “On the Decidability of Elementary Modal Logics.” ACM Transactions on Computational Logic, vol. 17, no. 1, 2, ACM, 2015, doi:10.1145/2817825.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar