Hostname: page-component-6bf8c574d5-mggfc Total loading time: 0 Render date: 2025-02-20T23:04:07.450Z Has data issue: false hasContentIssue false

Borel ranks and Wadge degrees of context free $\omega$-languages

Published online by Cambridge University Press:  11 October 2006

OLIVIER FINKEL
Affiliation:
Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7, 2 Place Jussieu 75251 Paris cedex 05, France Email: finkel@logique.jussieu.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Paper
Copyright
2006 Cambridge University Press