Fixpoint alternation: arithmetic, transition systems, and the binary tree
- 1 July 1999
- journal article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 33 (4-5) , 341-356
- https://doi.org/10.1051/ita:1999122
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 Niwiński.Keywords
This publication has 11 references indexed in Scilit:
- Tree automata, mu-calculus and determinacyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Theμ-calculus alternation-depth hierarchy is strict on binary treesRAIRO - Theoretical Informatics and Applications, 1999
- The modal mu-calculus alternation hierarchy is strictTheoretical Computer Science, 1998
- Fixed point characterization of infinite behavior of finite-state systemsTheoretical Computer Science, 1997
- A hierarchy theorem for the μ-calculusPublished by Springer Nature ,1996
- Automata for the modal μ-calculus and related resultsPublished by Springer Nature ,1995
- μ-definable sets of integersThe Journal of Symbolic Logic, 1993
- Verifying Temporal Properties of SystemsPublished by Springer Nature ,1992
- On fixed-point clonesPublished by Springer Nature ,1986
- Results on the propositional μ-calculusTheoretical Computer Science, 1983