Borel ranks and Wadge degrees of context free $\omega$-languages
Olivier Finkel · Mathematical Structures in Computer Science · 2006
We show that the Borel hierarchy of the class of context free $\omega$ -languages, or even of the class of $\omega$ -languages accepted by Büchi 1-counter automata, is the same as the Borel hierarchy of the class of $\omega$ -languages accepted by Turing machines with a Büchi acceptance condition. In particular, for each recursive non-null ordinal $\alpha$ , there exist some ${\bf \Sigma}^0_\alpha$ -complete and some ${\bf \Pi}^0_\alpha$ -complete $\omega$ -languages accepted by Büchi 1-counter automata. And the supremum of the set of Borel ranks of context free $\omega$ -languages is an ordinal $\gamma_2^1$ that is strictly greater than the first non-recursive ordinal $\omega_1^{\mathrm{CK}}$ . We then extend this result, proving that the Wadge hierarchy of context free $\omega$ -languages, or even of $\omega$ -languages accepted by Büchi 1-counter automata, is the same as the Wadge hierarchy of $\omega$ -languages accepted by Turing machines with a Büchi or a Muller acceptance condition.