| Identifiant de l'article : |
 |
ensl-00130246, version 1 |
|
|
| Identifiant arXiv : |
|
arXiv:math.LO/0702334 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
An Example of Pi^0_3-complete Infinitary Rational Relation |
|
|
| Auteur(s) : |
|
Olivier Finkel1 |
|
|
| Laboratoire : |
|
| 1 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| Résumé : |
|
We give in this paper an example of infinitary rational relation, accepted by a 2-tape Büchi automaton, which is Pi^0_3-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
Infinitary rational relations – topological properties – Borel hierarchy – Pi^0_3-complete set. |
|
|
| Référence interne : |
|
LIP Research Report n° 2007-09 |
|
|
Récupérer au format
