# Semantisches Browsen

Abstract The fully enriched mu-calculus is the exte … The fully enriched mu-calculus is the extension of the propositional mu-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched mu-calculus is known to be decidable and ExpTime-complete, it has recently been proved that the full calculus is undecidable. In this paper, we study the fragments of the fully enriched mu-calculus that are obtained by dropping at least one of the additional constructs. We show that, in all fragments obtained in this way, satisfiability is decidable and ExpTime-complete. Thus, we identify a family of decidable logics that are maximal (and incomparable) in expressive power. Our results are obtained by introducing two new automata models, showing that their emptyness problems are ExpTime-complete, and then reducing satisfiability in the relevant logics to this problem. The automata models we introduce are two-way graded alternating parity automata over infinite trees (2GAPT) and fully enriched automata (FEA) over infinite forests. The former are a common generalization of two incomparable automata models from the literature. The latter extend alternating automata in a similar way as the fully enriched mu-calculus extends the standard mu-calculus.calculus extends the standard mu-calculus.  + P. Bonatti + , A. Murano + , M. Vardi + , @inproceedings{ BoLuMuVa-ICALP06,  author = {P. {Bonatti} and C. {Lutz} and A. {Murano} and M. {Vardi}},  booktitle = {Proccedings of the 33rd International Colloquium on Automata, Languages and Programming, Part {II} ({ICALP'06})},  editor = {Michele {Bugliesi} and Bart {Preneel} and Vladimiro {Sassone} and Ingo {Wegener}},  pages = {540--551},  publisher = {Springer-Verlag},  series = {Lecture Notes in Computer Science},  title = {The Complexity of Enriched $\mu$-Calculi},  volume = {4052},  year = {2006},} Inproceedings  + Proccedings of the 33rd International Colloquium on Automata, Languages and Programming, Part II (ICALP'06)  + BoLuMuVa-ICALP06.pdf  + Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener  + Bonatti  + P.  + 540-551  + P. Bonatti, Carsten Lutz, A. Murano, M. Va … P. Bonatti, Carsten Lutz, A. Murano, M. Vardi