Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree

  • Julian C. Bradfield

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 Niwinski.
Published
1998-12-23
How to Cite
Bradfield, J. (1998). Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree. BRICS Report Series, 5(53). https://doi.org/10.7146/brics.v5i53.19499