Borel Ranks and Wadge Degrees of Context Free Omega Languages
| dc.creator | Finkel, Olivier | |
| dc.date | 2007-12-09 | |
| dc.date.accessioned | 2026-07-07T08:48:12Z | |
| dc.date.available | 2026-07-07T08:48:12Z | |
| dc.description | 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 every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega context free languages accepted by 1-counter Büchi automata, and the supremum of the set of Borel ranks of context free omega languages is the ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This very surprising result gives answers to questions of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621]. | |
| dc.identifier | https://arxiv.org/abs/0712.1359 | |
| dc.identifier | http://arxiv.org/abs/0712.1359 | |
| dc.identifier | Mathematical Structures in Computer Science 16 (5) (2006) 813-840 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143861 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Logic | |
| dc.title | Borel Ranks and Wadge Degrees of Context Free Omega Languages | |
| dc.type | text |