Borel Ranks and Wadge Degrees of Omega Context Free Languages
An error appeared in this paper and was corrected in the journal version published in MSCS, Volume 16(5), 2006. The supremum of the set of Borel ranks of context free omega languages is not the first non recursive ordinal but an ordinal gamma^1_2 which is strictly greater than the first non recursiv...
Main Author: | |
---|---|
Other Authors: | , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2005
|
Subjects: | |
Online Access: | https://hal.science/hal-00117508 https://hal.science/hal-00117508/document https://hal.science/hal-00117508/file/cie-05.pdf |
Summary: | An error appeared in this paper and was corrected in the journal version published in MSCS, Volume 16(5), 2006. The supremum of the set of Borel ranks of context free omega languages is not the first non recursive ordinal but an ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This follows from a result proved by A. S. Kechris, D. Marker and R. L. Sami, in [ Pi^1_1 Borel sets, Journal of Symbolic Logic, Volume 54 (3), p. 915-920, 1989 ]. International audience We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular, for each recursive non null ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega languages accepted by Büchi 1-counter automata. |
---|