Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2013.563
URN: urn:nbn:de:0030-drops-42195
URL: https://drops.dagstuhl.de/opus/volltexte/2013/4219/
Michaliszyn, Jakub ; Otop, Jan
Elementary Modal Logics over Transitive Structures
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{michaliszyn_et_al:LIPIcs:2013:4219,
author = {Jakub Michaliszyn and Jan Otop},
title = {{Elementary Modal Logics over Transitive Structures}},
booktitle = {Computer Science Logic 2013 (CSL 2013)},
pages = {563--577},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-60-6},
ISSN = {1868-8969},
year = {2013},
volume = {23},
editor = {Simona Ronchi Della Rocca},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4219},
URN = {urn:nbn:de:0030-drops-42195},
doi = {10.4230/LIPIcs.CSL.2013.563},
annote = {Keywords: Modal logic, Transitive frames, Elementary modal logics, Decidability}
}
| Keywords: | Modal logic, Transitive frames, Elementary modal logics, Decidability | |
| Seminar: | Computer Science Logic 2013 (CSL 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 02.09.2013 |
