Fixpoint alternation: arithmetic, transition systems, and the binary tree
J. C. Bradfield (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.