Simplifying the modal mu-calculus alternation hierarchy

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In [Bra96], the strictness of the modal mu-calculus alternation hierarchy was shown by transferring a hierarchy from arithmetic; the latter was a corollary of a deep and highly technical analysis of [Lub93]. In this paper, we show that the alternation hierarchy in arithmetic can be established by entirely elementary means; further, simple examples of strict alternation depth n formulae can be constructed, which in turn give very simple examples to separate the modal hierarchy. In addition, the winning strategy formulae of parity games are shown to be such examples.
Original languageEnglish
Title of host publicationSTACS 98
Subtitle of host publication15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998 Proceedings
EditorsMichel Morvan, Christoph Meinel, Daniel Krob
PublisherSpringer Berlin Heidelberg
Number of pages11
ISBN (Electronic)978-3-540-69705-3
ISBN (Print)978-3-540-64230-5
Publication statusPublished - 1998

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg

Fingerprint Dive into the research topics of 'Simplifying the modal mu-calculus alternation hierarchy'. Together they form a unique fingerprint.

Cite this