Fixpoint alternation: arithmetic, transition systems, and the binary tree

Research output: Contribution to journalArticlepeer-review

Abstract

We provide an elementary proof of the fixpoint alternation hierarchy in arithmetic, which in turn allows us to simplify the proof of the modal mu-calculus alternation hierarchy. We further show that the alternation hierarchy on the binary tree is strict, resolving a problem of Niwiński.
Original languageEnglish
Pages (from-to)341-356
Number of pages16
JournalRAIRO: Theoretical Informatics and Applications
Volume33
DOIs
Publication statusPublished - 1 Jul 1999

Keywords

  • Fixpoints
  • mu-calculus
  • alternation
  • modal logic

Fingerprint Dive into the research topics of 'Fixpoint alternation: arithmetic, transition systems, and the binary tree'. Together they form a unique fingerprint.

Cite this