Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
LATPub340
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.  +
Author P. Bonatti + , A. Murano + , M. Vardi + , Carsten Lutz +
BibTex
@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},
}
Bibtype Inproceedings  +
Booktitle Proccedings of the 33rd International Colloquium on Automata, Languages and Programming, Part II (ICALP'06)  +
Download BoLuMuVa-ICALP06.pdf  +
Editor Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener  +
ErsterAutorNachname Bonatti  +
ErsterAutorVorname P.  +
Forschungsgruppe Automatentheorie +
Pages 540-551  +
Publication text P. Bonatti, Carsten Lutz, A. Murano, M. Va
P. Bonatti, Carsten Lutz, A. Murano, M. Vardi<br/> '''[[LATPub340|<b>The Complexity of Enriched µ-Calculi</b>]]''' <br/>__NOTOC__In Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener, eds., <i>Proccedings of the 33rd International Colloquium on Automata, Languages and Programming, Part II (ICALP'06)</i>, volume 4052 of Lecture Notes in Computer Science, 540-551, 2006. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub340|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BoLuMuVa-ICALP06.pdf|Download]]
t; [[Media:BoLuMuVa-ICALP06.pdf|Download]]  +
Publication text en P. Bonatti, Carsten Lutz, A. Murano, M. Va
P. Bonatti, Carsten Lutz, A. Murano, M. Vardi<br/> '''[[LATPub340/en|<b>The Complexity of Enriched µ-Calculi</b>]]''' <br/>__NOTOC__In Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener, eds., <i>Proccedings of the 33rd International Colloquium on Automata, Languages and Programming, Part II (ICALP'06)</i>, volume 4052 of Lecture Notes in Computer Science, 540-551, 2006. Springer<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub340|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BoLuMuVa-ICALP06.pdf|Download]]
t; [[Media:BoLuMuVa-ICALP06.pdf|Download]]  +
Publisher Springer  +
Referiert 1  +
Series Lecture Notes in Computer Science  +
Title The Complexity of Enriched µ-Calculi  +
To appear 0  +
Type inproceedings  +
Volume 4052  +
Year 2006  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
LATPub340 + , LATPub340 + , LATPub340 + , LATPub340 + , LATPub340 + , LATPub340 + , LATPub340 + , LATPub340 +
Kategorien Inproceedings , Publikation
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
25 März 2015 14:34:05  +
verstecke Attribute die hierhin verlinken 
LATPub340/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.