Universität Bremen  
  FB 3  
  Group BKB > Publications > Search > Deutsch
English
 

Publications Search - Details

 
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

 Back to result list
 
   
Author: Automatically generated page
 
  Group BKB 
Last updated: February 23, 2006   impressum