Borel hierarchy and omega context free languages
We give in this paper additional answers to questions of Lescow and Thomas (A decade of Concurrency, Lecture Notes in Computer Science, Vol. 803, Springer, Berlin, 1994, pp. 583621), proving topological properties of omega context free languages ((omega-CFL) which extend those of O.. Finkel (Theoret. Comput. Sci. 262 (1-2) (2001) 669-697): there exist some omega-CFL which are non Borel sets and one cannot decide whether an omega-CFL is a Borel set. We give also an answer to a question of Niwinski (Problem on omega-Powers Posed in the Proceedings of the Workshop "Logics and Recognizable Sets, 1990") and of Simonnet (Automates et Theorie Descriptive, Ph.D. Thesis, Universite Paris 7, 1992) about (omega-powers of finitary languages, giving an example of a finitary context free language L such that L-omega is not a Borel set. Then we prove some recursive analogues to preceding properties: in particular one cannot decide whether an omega-CFL is an arithmetical set. Finally we extend some results to context free sets of infinite trees. (C) 2002 Elsevier Science B.V. All rights reserved.
borel hierarchy context free omega-languages topological complexity analytic sets