Elementary Modal Logics over Transitive Structures

Authors Jakub Michaliszyn, Jan Otop



PDF
Thumbnail PDF

File

LIPIcs.CSL.2013.563.pdf
  • Filesize: 444 kB
  • 15 pages

Document Identifiers

Author Details

Jakub Michaliszyn
Jan Otop

Cite AsGet BibTex

Jakub Michaliszyn and Jan Otop. Elementary Modal Logics over Transitive Structures. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 563-577, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.CSL.2013.563

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.
Keywords
  • Modal logic
  • Transitive frames
  • Elementary modal logics
  • Decidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail