Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.264
URN: urn:nbn:de:0030-drops-33495
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3349/
Kieronski, Emanuel ; Michaliszyn, Jakub ; Otop, Jan
Modal Logics Definable by Universal Three-Variable Formulas
| pdf-format: |
|
Abstract
We consider the satisfiability problem for modal logic over classes of structures definable by universal first-order formulas with three variables. We exhibit a simple formula for which the problem is undecidable. This improves an earlier result in which nine variables were used. We also show that for classes defined by three-variable, universal Horn formulas the problem is decidable. This subsumes decidability results for many natural modal logics, including T, B, K4, S4, S5.
BibTeX - Entry
@InProceedings{kieronski_et_al:LIPIcs:2011:3349,
author = {Emanuel Kieronski and Jakub Michaliszyn and Jan Otop},
title = {{Modal Logics Definable by Universal Three-Variable Formulas}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {264--275},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-34-7},
ISSN = {1868-8969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3349},
URN = {urn:nbn:de:0030-drops-33495},
doi = {10.4230/LIPIcs.FSTTCS.2011.264},
annote = {Keywords: modal logic, decidability}
}
| Keywords: | modal logic, decidability | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) | |
| Issue date: | 2011 | |
| Date of publication: | 01.12.2011 |
