On the expressivity of the modal mu-calculus

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


We analyse the complexity of the sets of states, in certain classes of infinite systems, that satisfy formulae of the modal mu-calculus. Improving on some of our earlier results, we establish a strong upper bound (namely Δ 2 1). We also establish various lower bounds and restricted upper bounds, incidentally providing another proof that the mu-calculus alternation hierarchy does not collapse at level 2.
Original languageEnglish
Title of host publicationSTACS 96
Subtitle of host publication13th Annual Symposium on Theoretical Aspects of Computer Science Grenoble, France, February 22–24, 1996 Proceedings
EditorsClaude Puech, Rüdiger Reischuk
PublisherSpringer Berlin Heidelberg
Number of pages14
ISBN (Electronic)978-3-540-49723-3
ISBN (Print)978-3-540-60922-3
Publication statusPublished - 1996

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg


  • descriptive complexity
  • logic in computer science
  • verification
  • temporal logic


Dive into the research topics of 'On the expressivity of the modal mu-calculus'. Together they form a unique fingerprint.

Cite this