Wadge Degrees of Infinitary Rational Relations

Abstract : 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 $\alpha$, there exist some $\Sigma^0_\alpha$-complete and some $\Pi^0_\alpha$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal $\gamma^1_2$ which is strictly greater than the first non-recursive ordinal $\omega_1^{CK}$. This very surprising result gives answers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994).
Type de document :
Article dans une revue
Mathematics in Computer Science, Springer, 2008, 2 (1), pp.85-102. 〈10.1007/s11786-008-0045-7〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00274931
Contributeur : Olivier Finkel <>
Soumis le : lundi 21 avril 2008 - 21:11:14
Dernière modification le : mardi 16 janvier 2018 - 16:16:47
Document(s) archivé(s) le : vendredi 21 mai 2010 - 01:55:31

Fichiers

Wadge-degrees-rat-relations.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Finkel. Wadge Degrees of Infinitary Rational Relations. Mathematics in Computer Science, Springer, 2008, 2 (1), pp.85-102. 〈10.1007/s11786-008-0045-7〉. 〈ensl-00274931〉

Partager

Métriques

Consultations de la notice

195

Téléchargements de fichiers

97