On the expressivity of the modal mu-calculus

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

Abstract

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
Pages477-490
Number of pages14
Volume1046
ISBN (Electronic)978-3-540-49723-3
ISBN (Print)978-3-540-60922-3
DOIs
Publication statusPublished - 1996

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume1046

Keywords

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

Fingerprint

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

Cite this