Computer Science – Logic in Computer Science
Scientific paper
2011-05-11
LMCS 7 (3), 3, 2011
Computer Science
Logic in Computer Science
Scientific paper
10.2168/LMCS-7(3:03)2011
The coalgebraic approach to modal logic provides a uniform framework that captures the semantics of a large class of structurally different modal logics, including e.g. graded and probabilistic modal logics and coalition logic. In this paper, we introduce the coalgebraic mu-calculus, an extension of the general (coalgebraic) framework with fixpoint operators. Our main results are completeness of the associated tableau calculus and EXPTIME decidability for guarded formulas. Technically, this is achieved by reducing satisfiability to the existence of non-wellfounded tableaux, which is in turn equivalent to the existence of winning strategies in parity games. Our results are parametric in the underlying class of models and yield, as concrete applications, previously unknown complexity bounds for the probabilistic mu-calculus and for an extension of coalition logic with fixpoints.
Cirstea Corina
Kupke Clemens
Pattinson Dirk
No associations
LandOfFree
EXPTIME Tableaux for the Coalgebraic mu-Calculus 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 EXPTIME Tableaux for the Coalgebraic mu-Calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and EXPTIME Tableaux for the Coalgebraic mu-Calculus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-612025