License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1356
URN: urn:nbn:de:0030-drops-13561
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1356/
Hemaspaandra, Edith ;
Schnoor, Henning
On the Complexity of Elementary Modal Logics
Abstract
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
@InProceedings{hemaspaandra_et_al:LIPIcs:2008:1356,
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 = {http://drops.dagstuhl.de/opus/volltexte/2008/1356},
URN = {urn:nbn:de:0030-drops-13561},
doi = {10.4230/LIPIcs.STACS.2008.1356},
annote = {Keywords: }
}
|
Collection: |
|
25th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
06.02.2008 |
