Borel Ranks and Wadge Degrees of Omega Context Free Languages

• Main Author: Finkel, Olivier
• Other Authors: Équipe de Logique Mathématique (ELM), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), S. Barry Cooper, Benedikt Löwe, and Leen Torenvliet
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2005
• Subjects: [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]; [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT]; [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; [MATH.MATH-LO]Mathematics [math]/Logic [math.LO]; sami
• Online Access: https://hal.science/hal-00117508; https://hal.science/hal-00117508/document; https://hal.science/hal-00117508/file/cie-05.pdf

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.