PSPACE Bounds for Rank-1 Modal Logics

Details PSPACE Bounds for Rank-1 Modal Logics PSPACE Bounds for Rank-1 Modal Logics

2007-06-27

arxiv.org/abs/0706.4044v1

ACM Transactions on Computational Logic 10 (2:13), pp. 1-33, 2009

Computer Science

Logic in Computer Science

Scientific paper

10.1145/1462179.1462185

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 rank-1 logics enjoy a shallow model property and thus are, under mild assumptions on the format of their axiomatisation, in PSPACE. This leads to a unified derivation of tight PSPACE-bounds for a number of logics including K, KD, coalition logic, graded modal logic, majority logic, and probabilistic modal logic. Our generic algorithm moreover finds tableau proofs that witness pleasant proof-theoretic properties including a weak subformula property. 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.

Affiliated with

Also associated with

No associations

Rating

PSPACE Bounds for Rank-1 Modal Logics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with PSPACE Bounds for Rank-1 Modal Logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PSPACE Bounds for Rank-1 Modal Logics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256127