Simplifying the modal mu-calculus alternation hierarchy

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

Abstract

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
Pages39-49
Number of pages11
Volume1373
ISBN (Electronic)978-3-540-69705-3
ISBN (Print)978-3-540-64230-5
DOIs
Publication statusPublished - 1998

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume1373

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

Cite this