On the Length of the Wadge Hierarchy of ω-Context-Free Languages
Olivier Finkel · 2005
We prove in this paper that the length of the Wadge hierarchy of $\omega$-context-free languages is greater than the Cantor ordinal $\epsilon_\omega$, which is the $\omega^{th}$ fixed point of the ordinal exponentiation of base $\omega$. We show also that there exist some $\Sigma_$\omega$^0$-complete $\omega$-context-free languages, improving previous results on w-context-free languages and the Borel hierarchy.