Topological Complexity of Locally Finite omega-Languages - Archive ouverte HAL Access content directly
Journal Articles Archive for Mathematical Logic Year : 2008

Topological Complexity of Locally Finite omega-Languages

(1)
1

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].
Fichier principal
Vignette du fichier
LOC-AML.pdf (269.06 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ensl-00160798 , version 1 (08-07-2007)
ensl-00160798 , version 2 (10-07-2007)

Identifiers

  • HAL Id : ensl-00160798 , version 2

Cite

Olivier Finkel. Topological Complexity of Locally Finite omega-Languages. Archive for Mathematical Logic, 2008, 47 (6), pp.625-651. ⟨ensl-00160798v2⟩
91 View
134 Download

Share

Gmail Facebook Twitter LinkedIn More