When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1356
URN: urn:nbn:de:0030-drops-13561
Go to the corresponding LIPIcs Volume Portal

Hemaspaandra, Edith ; Schnoor, Henning

On the Complexity of Elementary Modal Logics

22011.HemaspaandraEdith.Paper.1356.pdf (0.3 MB)


Modal 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.

BibTeX - Entry

  author =	{Edith Hemaspaandra and Henning Schnoor},
  title =	{{On the Complexity of Elementary Modal Logics}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{349--360},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-13561},
  doi =		{},
  annote =	{Keywords: }

Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI