2026-08-11T13:18:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3349 2024-03-06T10:34:05Z ddc:004 open_access

Modal Logics Definable by Universal Three-Variable Formulas Kieronski, Emanuel Michaliszyn, Jakub Otop, Jan modal logic decidability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emanuel Kieronski and Jakub Michaliszyn and Jan Otop 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.264 urn:nbn:de:0030-drops-33495 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.264 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode