On omega context free languages which are Borel sets of infinite rank
✍ Scribed by Olivier Finkel
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 296 KB
- Volume
- 299
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
This paper is a continuation of the study of topological properties of omega context free languages (!-CFL). We proved in (Topological properties of omega context free languages, Theoretical Computer Science, 262 (1-2) (2001) 669-697) that the class of !-CFL exhausts the ÿnite ranks of the Borel hierarchy, and in (Borel hierarchy and omega context free languages, Theoretical Computer Science, to appear) that there exist some !-CFL which are analytic but non Borel sets. We prove here that there exist some omega context free languages which are Borel sets of inÿnite (but not ÿnite) rank, giving additional answer to questions of Lescow and Thomas [Logical speciÿcations of inÿnite computations in: "A Decade of Concurrency" (J.W. de Bakker et al. (Eds.), Springer LNCS 803 (1994) 583-621).