Borel Ranks and Wadge Degrees of Context Free Omega Languages

Details Borel Ranks and Wadge Degrees of Context Free Omega Languages Borel Ranks and Wadge Degrees of Context Free Omega Languages

2007-12-09

arxiv.org/abs/0712.1359v1

Mathematical Structures in Computer Science 16 (5) (2006) 813-840

Computer Science

Logic in Computer Science

Scientific paper

We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter B\"uchi automata have the same accepting power than Turing machines equipped with a B\"uchi acceptance condition. In particular, for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega context free languages accepted by 1-counter B\"uchi automata, and the supremum of the set of Borel ranks of context free omega languages is the ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This very surprising result gives answers to questions of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621].

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-404631