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 [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994), 583-621]. We give also a (partial) answer to a question of Simonnet about omega powers of finitary languages. We show that Büchi-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.

Data and Resources

Additional Info

Field Value
Source ISSN: 0304-3975
Author Finkel, Olivier
Maintainer CCSD
Last Updated May 8, 2026, 18:16 (UTC)
Created May 8, 2026, 18:16 (UTC)
Identifier hal-00089055
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Équipe de Logique Mathématique (ELM) ; Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
creator Finkel, Olivier
date 2001-05-08T00:00:00
harvest_object_id 257e2bf3-54ca-41d2-a927-7d7d79afcf96
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-09T00:00:00
set_spec type:ART