{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T15:07:08Z","timestamp":1775056028152,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,9,22]],"date-time":"2008-09-22T00:00:00Z","timestamp":1222041600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The fully enriched &amp;mu;-calculus is the extension of the propositional\n&amp;mu;-calculus with inverse programs, graded modalities, and nominals. While\nsatisfiability in several expressive fragments of the fully enriched\n&amp;mu;-calculus is known to be decidable and ExpTime-complete, it has recently\nbeen proved that the full calculus is undecidable. In this paper, we study the\nfragments of the fully enriched &amp;mu;-calculus that are obtained by dropping at\nleast one of the additional constructs. We show that, in all fragments obtained\nin this way, satisfiability is decidable and ExpTime-complete. Thus, we\nidentify a family of decidable logics that are maximal (and incomparable) in\nexpressive power. Our results are obtained by introducing two new automata\nmodels, showing that their emptiness problems are ExpTime-complete, and then\nreducing satisfiability in the relevant logics to these problems. The automata\nmodels we introduce are two-way graded alternating parity automata over\ninfinite trees (2GAPTs) and fully enriched automata (FEAs) over infinite\nforests. The former are a common generalization of two incomparable automata\nmodels from the literature. The latter extend alternating automata in a similar\nway as the fully enriched &amp;mu;-calculus extends the standard &amp;mu;-calculus.<\/jats:p>","DOI":"10.2168\/lmcs-4(3:11)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:23:40Z","timestamp":1231496620000},"source":"Crossref","is-referenced-by-count":25,"title":["The Complexity of Enriched Mu-Calculi"],"prefix":"10.46298","volume":"Volume 4, Issue 3","author":[{"given":"Piero A.","family":"Bonatti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8791-6702","authenticated-orcid":false,"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4876-3448","authenticated-orcid":false,"given":"Aniello","family":"Murano","sequence":"additional","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,9,22]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/993\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/993\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:49Z","timestamp":1681243249000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,22]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(3:11)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0809.0360","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0809.0360","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1607.03354","asserted-by":"subject"},{"id-type":"doi","id":"10.4204\/eptcs.218.1","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1607.03354","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,22]]},"article-number":"993"}}