| Publication type: |
Article in Proceedings |
| Author: |
Lutz Schröder, Dirk Pattinson |
| Editor: |
Rajeev Alur |
| Title: |
PSPACE Bounds for Rank 1 Modal Logics |
| Book / Collection title: |
Logic in Computer Science (LICS 06) |
| Page(s): |
231 – 240 |
| Year published: |
2006 |
| Publisher: |
IEEE |
| Abstract: |
For lack of general algorithmic methods that apply to wide classes of
logics, establishing a complexity bound for a given modal logic is often
a laborious task.
The present work is a step towards a general theory of the complexity of
modal logics.
Our main result is that all mboxrank-1 logics enjoy a shallow model
property and thus are, under mild assumptions on the format of their
axiomatization, in PSPACE. This leads not only to a unified
derivation of (known) tight PSPACE-bounds for a number of logics
including K, coalition logic, and graded modal logic (and to a new
algorithm in the latter case), but also to a previously unknown tight
PSPACE-bound for probabilistic modal logic, with rational probabilities
coded in binary. This generality is made possible by a coalgebraic
semantics, which conveniently abstracts from the details of a given
model class and thus allows covering a broad range of logics in a
uniform way.
|
| Internet: |
http://dx.doi.org/10.1109/LICS.2006.44 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~lschrode/papers/CMLpspace.pdf |
| Keywords: |
coalgebra modal logic PSPACE shallow models |
| Note / Comment: |
Presentation slides available |
| Status: |
Reviewed |
| Last updated: |
18. 06. 2008 |
