Elementary Modal Logics over Transitive Structures

Michaliszyn, Jakub and Otop, Jan (2013) Elementary Modal Logics over Transitive Structures. In: Elementary Modal Logics over Transitive Structures. LIPIcs, 23 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, pp. 563-577. ISBN 978-3-939897-60-6

[img] Text
39.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2016-136-v1+2]
Download (444Kb)

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.

Item Type: Book Section
DOI: 10.4230/LIPIcs.CSL.2013.563
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Henzinger Group
Depositing User: Jan Otop
Date Deposited: 25 Jul 2013 15:46
Last Modified: 14 Mar 2016 16:58
URI: https://repository.ist.ac.at/id/eprint/136

Actions (login required)

View Item View Item