HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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].
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00160798
Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Tuesday, July 10, 2007 - 9:24:20 AM
Last modification on : Saturday, September 11, 2021 - 3:17:26 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:54:56 PM

File

LOC-AML.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

87

Files downloads

115