| Identifiant de l'article : |
 |
ensl-00216624, version 1 |
|
|
| Identifiant arXiv : |
|
arXiv:0801.3912 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
On the Continuity Set of an omega Rational Function |
|
|
| Auteur(s) : |
|
Olivier Carton1, Olivier Finkel2, Pierre Simonnet3 |
|
|
| Laboratoire : |
|
| 1 : |
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications |
|
| 2 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 3 : |
SPE - Sciences pour l'environnement |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| Résumé : |
|
In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function F has at least one point of continuity and that its continuity set C(F) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore we prove that any rational Pi^0_2-subset of X^omega for some alphabet X is the continuity set C(F) of an omega-rational synchronous function F defined on X^omega. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
Infinitary rational relations – Omega rational functions – Topology – Points of continuity – Decision problems – Omega rational languages – Omega context-free languages |
|
|
| Commentaire : |
|
Dedicated to Serge Grigorieff on the occasion of his 60th Birthday |
|
|
Récupérer au format
