Topological Complexity of Locally Finite omega-Languages

Abstract : 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].
Type de document :
Article dans une revue
Archive for Mathematical Logic, Springer Verlag, 2008, pp.625-651
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00160798
Contributeur : Olivier Finkel <>
Soumis le : mardi 10 juillet 2007 - 09:24:20
Dernière modification le : mardi 24 avril 2018 - 13:52:45
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:54:56

Fichier

LOC-AML.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00160798, version 2

Collections

Citation

Olivier Finkel. Topological Complexity of Locally Finite omega-Languages. Archive for Mathematical Logic, Springer Verlag, 2008, pp.625-651. 〈ensl-00160798v2〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

99