文章基本信息

标题：On the Complexity of Elementary Modal Logics
本地全文：下载
作者：Edith Hemaspaandra ; Henning Schnoor
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：349-360
DOI：10.4230/LIPIcs.STACS.2008.1356
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.