On the Complexity of Elementary Modal Logics

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
Full version of STACS 2008 paper

Keywords

Computational Complexity, Logic in Computer Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/154750

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.1884
 http://arxiv.org/abs/0802.1884

Collections

arXiv