| Art der Veröffentlichung: |
Artikel in Konferenzband |
| Autor: |
Lutz Schröder, Dirk Pattinson |
| Herausgeber: |
Rajeev Alur |
| Titel: |
PSPACE Bounds for Rank 1 Modal Logics |
| Buch / Sammlungs-Titel: |
Logic in Computer Science (LICS 06) |
| Seite(n): |
231 – 240 |
| Erscheinungsjahr: |
2006 |
| Verleger: |
IEEE |
| Abstract / Kurzbeschreibung: |
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 |
| Schlagworte: |
coalgebra modal logic PSPACE shallow models |
| Anmerkung / Hinweis: |
Presentation slides available |
| Status: |
Reviewed |
| Letzte Aktualisierung: |
18. 06. 2008 |
