Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree
AbstractWe 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.
How to Cite
Bradfield, J. C. (1998). Fixpoint Alternation: Arithmetic, Transition Systems, and the Binary Tree. BRICS Report Series, 5(53). https://doi.org/10.7146/brics.v5i53.19499
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.