|
Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary
Tree
Julian C. Bradfield December 1998 |
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 Available as PostScript, PDF. |