Borel Hierarchy and Omega Context Free Languages

2011/01/18 by Olivier Finkel · 1 citation
Computer Science · Mathematics · #cs.LO #math.LO

paper · pdf

published as Theoretical Computer Science 290 (3) (2003) 1385-1405

arxiv created 2011/01/18 · arxiv updated 2011/01/20

Abstract

We give in this paper additional answers to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994), 583-621], proving new topological properties of omega context free languages : 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 questions of Niwinski and Simonnet 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.

Cited by

• Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words