Topological properties of omega context-free languages
This paper is a study of topological properties of omega context-free languages (omega -CFL). We first extend some decidability results for the deterministic ones (omega -DCFL), proving that one can decide whether an omega -DCFL is in a given Borel class, or in the Wadge class of a given omega -regular language. We prove that omega -CFL exhaust the hierarchy of Borel sets of finite rank, and that one cannot decide the borel class of an omega -CFL, giving an answer to a question of Lescow and Thomas (A Decade of Concurrency, Springer Lecture Notes in Computer Science, vol. 803, Springer, Berlin, 1994, pp. 583-621). We give also a (partial) answer to a question of Simmonet (Automates et theorie descriptive, Ph.D. Thesis, Universite Paris 7, March 1992) about omega powers of finitary languages. We show that Buchi-Landweber's Theorem cannot be extended to even closed omega -CFL: in a Gale-Stewart game with a (closed) omega -CFL winning set, one cannot decide which player has a winning strategy. From the proof of topological properties we derive some arithmetical properties of omega -CFL. (C) 2001 Elsevier Science B.V. All rights reserved.
topological properties omega context-free languages borel class wadge class decide the borel class omega powers gale-stewart game arithmetical properties