Wadge Degrees of Infinitary Rational Relations
| dc.creator | Finkel, Olivier | |
| dc.date | 2008-04-21 | |
| dc.date.accessioned | 2026-07-07T12:23:31Z | |
| dc.date.available | 2026-07-07T12:23:31Z | |
| dc.description | We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as Turing machines equipped with a Büchi acceptance condition. The Borel and the Wadge hierarchies of the class RAT_omega of infinitary rational relations accepted by 2-tape Büchi automata are equal to the Borel and the Wadge hierarchies of omega-languages accepted by real-time Büchi 1-counter automata or by Büchi Turing machines. In particular, for every non-null recursive ordinal $α$, there exist some $Σ^0_α$-complete and some $Π^0_α$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal $γ^1_2$ which is strictly greater than the first non-recursive ordinal $ω_1^{CK}$. This very surprising result gives answers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994). | |
| dc.description | to appear in the journal Mathematics in Computer Science, in a Special Issue on Intensional Programming & Semantics, in honour of Bill Wadge on the occasion of his 60th cycle | |
| dc.identifier | https://arxiv.org/abs/0804.3266 | |
| dc.identifier | http://arxiv.org/abs/0804.3266 | |
| dc.identifier | Mathematics in Computer Science 1, 2 (2008) 85-102 | |
| dc.identifier | doi:10.1007/s11786-008-0045-7 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/214017 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic | |
| dc.title | Wadge Degrees of Infinitary Rational Relations | |
| dc.type | text |