Topological complexity of locally finite omega-languages

摘要

Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009-1026, 1988]. These languages are defined by local sentences and extend omega-languages accepted by Buchi 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 Theorie Descriptive, Ph.D. Thesis. Universite Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1-2):85-105, 2001].