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

Julian C. Bradfield

December 1998


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

Available as PostScript, PDF.


Last modified: 2003-06-08 by webmaster.