Topological Properties of Omega Context Free Languages
type: Dataset
description: 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.
issued: 2026-05-08T18:16:38.557173
language: en
modified: 2026-05-08T18:16:38.557178
contact point: Organization
  fn: CCSD
keyword: arithmetical-class
keyword: borel-class
keyword: decision-problems
keyword: gale-stewart-game
keyword: infoeu-reposemanticsarticle
keyword: infoinfo-locomputer-science-cslogic-in-computer-science-cslo
keyword: journal-articles
keyword: omega-context-free-languages
keyword: omega-powers
keyword: topological-properties
keyword: wadge-class
landing page: 0304-3975

Topological Properties of Omega Context Free Languages
type: Distribution
format: HTML
issued: 2026-05-08T18:16:38.585116
modified: 2026-05-08T18:16:38.544602
access URL: https://hal.science/hal-00089055

test_moissonnage_selune
type: Agent