Elementary modal logics over transitive structures
Michaliszyn J, Otop J. 2013. Elementary modal logics over transitive structures. 23, 563–577.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Michaliszyn, Jakub;
Otop, JanISTA
Department
Series Title
LIPIcs
Abstract
We show that modal logic over universally first-order definable classes of transitive frames is decidable. More precisely, let K be an arbitrary class of transitive Kripke frames definable by a universal first-order sentence. We show that the global and finite global satisfiability problems of modal logic over K are decidable in NP, regardless of choice of K. We also show that the local satisfiability and the finite local satisfiability problems of modal logic over K are decidable in NEXPTIME.
Publishing Year
Date Published
2013-09-01
Volume
23
Page
563 - 577
Conference
CSL: Computer Science Logic
Conference Location
Torino, Italy
Conference Date
2013-09-02 – 2013-09-05
IST-REx-ID
Cite this
Michaliszyn J, Otop J. Elementary modal logics over transitive structures. 2013;23:563-577. doi:10.4230/LIPIcs.CSL.2013.563
Michaliszyn, J., & Otop, J. (2013). Elementary modal logics over transitive structures. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.563
Michaliszyn, Jakub, and Jan Otop. “Elementary Modal Logics over Transitive Structures.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.563.
J. Michaliszyn and J. Otop, “Elementary modal logics over transitive structures,” vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 563–577, 2013.
Michaliszyn J, Otop J. 2013. Elementary modal logics over transitive structures. 23, 563–577.
Michaliszyn, Jakub, and Jan Otop. Elementary Modal Logics over Transitive Structures. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 563–77, doi:10.4230/LIPIcs.CSL.2013.563.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
IST-2016-136-v1+2_39.pdf
454.92 KB
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
e0732e73a8b1e39483df7717d53e3e35
Google Scholar