×

Borel ranks and Wadge degrees of context free \(\omega\)-languages. (English) Zbl 1121.03047

In this interesting note, the author proves that the Borel hierarchy of the class of \(\omega\) context-free languages is the same as the Borel hierarchy of the class of \(\omega\)-languages accepted by Turing machines with the usual Büchi acceptance criteria. Such results are then extended to the Wadge hierarchy of context-free \(\omega\)-languages; viz., this Wadge hierarchy is the same as the Wadge hierarchy of \(\omega\)-languages accepted by Turing machines with either a Büchi or a Muller acceptance criterion. Here several results of W. Wadge are refined from his 1983 Ph.D. thesis at the University of California, Berkeley. The author’s proofs use several different methods from this research area. The reviewer believes that an “optimal mix” of the methods will be useful for the effective construction of \(\omega\)-languages and deep investigations of topological properties of infinitary rational relations.

MSC:

03D05 Automata and formal grammars in connection with logical questions
03E15 Descriptive set theory
68Q45 Formal languages and automata
03D10 Turing machines and related notions
Full Text: DOI