On the Length of the Wadge Hierarchy of Omega Context Free Languages

Details On the Length of the Wadge Hierarchy of Omega Context Free Languages On the Length of the Wadge Hierarchy of Omega Context Free Languages

2008-01-03

arxiv.org/abs/0801.0534v1

Journal of Automata, Languages and Combinatorics 10 (4) (2005) 439-464

Computer Science

Logic in Computer Science

Scientific paper

We prove in this paper that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal epsilon_omega, which is the omega-th fixed point of the ordinal exponentiation of base omega. The same result holds for the conciliating Wadge hierarchy, defined by J. Duparc, of infinitary context free languages, studied by D. Beauquier. We show also that there exist some omega context free languages which are Sigma^0_omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.

Affiliated with

Also associated with

No associations

Rating

On the Length of the Wadge Hierarchy of 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 On the Length of the Wadge Hierarchy of Omega Context Free Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Length of the Wadge Hierarchy of Omega Context Free Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-611254