2026-07-20T15:08:01Z https://drops.dagstuhl.de/oai

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

Elementary Modal Logics over Transitive Structures Michaliszyn, Jakub Otop, Jan Modal logic Transitive frames Elementary modal logics Decidability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Michaliszyn and Jan Otop 2013 Is Part Of LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2013.563 urn:nbn:de:0030-drops-42195 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.563 eng https://creativecommons.org/licenses/by/3.0/legalcode