| Identifiant de l'article : |
 |
ensl-00274931, version 1 |
|
|
| Identifiant arXiv : |
|
arXiv:0804.3266 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
Wadge Degrees of Infinitary Rational Relations |
|
|
| Auteur(s) : |
|
Olivier Finkel1, 2 |
|
|
| Laboratoire : |
|
| 1 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2 : |
ELM - Équipe de Logique Mathématique |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| Résumé : |
|
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). |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
2-tape Büchi automata – infinitary rational relations – Cantor topology – topological complexity – Wadge hierarchy – Wadge degrees – Wadge games – Borel hierarchy – complete sets. |
|
|
| Commentaire : |
|
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. |
|
|
| Référence interne : |
|
LIP Research Report RR 2008-14 |
|
|
Récupérer au format
