| Identifiant de l'article : |
 |
ensl-00160798, version 2 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
Topological Complexity of Locally Finite omega-Languages |
|
|
| 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é : |
|
Locally finite omega-languages were introduced by Ressayre in [Formal Languages defined by the Underlying Structure of their Words, Journal of Symbolic Logic, 53 (4), December 1988, p. 1009-1026]. These languages are defined by local sentences and extend omega-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite omega languages are analytic sets, the class LOC_omega of locally finite omega-languages meets all finite levels of the Borel hierarchy and there exist some locally finite omega-languages which are Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet [Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992] and of Duparc, Finkel, and Ressayre [Computer Science and the Fine Structure of Borel Sets, Theoretical Computer Science, Volume 257 (1-2), 2001, p.85-105]. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
Local sentences – Locally finite omega-languages – Topological complexity – Borel hierarchy – Analytic sets |
|
|
| Commentaire : |
|
to appear in Archive for Mathematical Logic |
|
|
| Référence interne : |
|
LIP Research Report n° RR 2007-34 |
|
|
Récupérer au format
