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.archives-ouvertes.fr/hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508/document https://hal.archives-ouvertes.fr/hal-00117508/file/cie-05.pdf |
id |
ftccsdartic:oai:HAL:hal-00117508v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-00117508v1 2023-05-15T18:12:18+02:00 Borel Ranks and Wadge Degrees of Omega Context Free Languages Finkel, Olivier É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 2005 https://hal.archives-ouvertes.fr/hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508/document https://hal.archives-ouvertes.fr/hal-00117508/file/cie-05.pdf en eng HAL CCSD Springer hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508/document https://hal.archives-ouvertes.fr/hal-00117508/file/cie-05.pdf info:eu-repo/semantics/OpenAccess Proceedings of New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. https://hal.archives-ouvertes.fr/hal-00117508 2005, pp.129-138 [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] info:eu-repo/semantics/conferenceObject Conference papers 2005 ftccsdartic 2020-12-26T19:02:39Z 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. Conference Object sami Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
[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] |
spellingShingle |
[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] Finkel, Olivier Borel Ranks and Wadge Degrees of Omega Context Free Languages |
topic_facet |
[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] |
description |
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. |
author2 |
É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 |
author |
Finkel, Olivier |
author_facet |
Finkel, Olivier |
author_sort |
Finkel, Olivier |
title |
Borel Ranks and Wadge Degrees of Omega Context Free Languages |
title_short |
Borel Ranks and Wadge Degrees of Omega Context Free Languages |
title_full |
Borel Ranks and Wadge Degrees of Omega Context Free Languages |
title_fullStr |
Borel Ranks and Wadge Degrees of Omega Context Free Languages |
title_full_unstemmed |
Borel Ranks and Wadge Degrees of Omega Context Free Languages |
title_sort |
borel ranks and wadge degrees of omega context free languages |
publisher |
HAL CCSD |
publishDate |
2005 |
url |
https://hal.archives-ouvertes.fr/hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508/document https://hal.archives-ouvertes.fr/hal-00117508/file/cie-05.pdf |
genre |
sami |
genre_facet |
sami |
op_source |
Proceedings of New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. https://hal.archives-ouvertes.fr/hal-00117508 2005, pp.129-138 |
op_relation |
hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508 https://hal.archives-ouvertes.fr/hal-00117508/document https://hal.archives-ouvertes.fr/hal-00117508/file/cie-05.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766184847866331136 |