Borel Hierarchy and Omega Context Free Languages

Details Borel Hierarchy and Omega Context Free Languages Borel Hierarchy and Omega Context Free Languages

2011-01-18

arxiv.org/abs/1101.3443v1

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

Computer Science

Logic in Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Borel Hierarchy and Omega Context Free Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Borel Hierarchy and Omega Context Free Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Borel Hierarchy and Omega Context Free Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286938