On the Complexity of Elementary Modal Logics

Simple item page
dc.creatorHemaspaandra, Edith
dc.creatorSchnoor, Henning
dc.date2008-02-13
dc.date.accessioned2026-07-07T09:20:32Z
dc.date.available2026-07-07T09:20:32Z
dc.descriptionModal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a very general classification for a wide class of relevant logics: Many important subclasses of modal logics can be obtained by restricting the allowed models with first-order Horn formulas. We show that the satisfiability problem for each of these logics is either NP-complete or PSPACE-hard, and exhibit a simple classification criterion. Further, we prove matching PSPACE upper bounds for many of the PSPACE-hard logics.
dc.descriptionFull version of STACS 2008 paper
dc.identifierhttps://arxiv.org/abs/0802.1884
dc.identifierhttp://arxiv.org/abs/0802.1884
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154750
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.titleOn the Complexity of Elementary Modal Logics
dc.typetext

Files

Collections

arXiv