Computer Science – Logic in Computer Science
Scientific paper
2008-04-21
Mathematics in Computer Science 1, 2 (2008) 85-102
Computer Science
Logic in Computer Science
to appear in the journal Mathematics in Computer Science, in a Special Issue on Intensional Programming & Semantics, in honour
Scientific paper
10.1007/s11786-008-0045-7
We show that, from the topological point of view, 2-tape B\"uchi automata have the same accepting power as Turing machines equipped with a B\"uchi acceptance condition. The Borel and the Wadge hierarchies of the class RAT_omega of infinitary rational relations accepted by 2-tape B\"uchi automata are equal to the Borel and the Wadge hierarchies of omega-languages accepted by real-time B\"uchi 1-counter automata or by B\"uchi Turing machines. In particular, for every non-null recursive ordinal $\alpha$, there exist some $\Sigma^0_\alpha$-complete and some $\Pi^0_\alpha$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal $\gamma^1_2$ which is strictly greater than the first non-recursive ordinal $\omega_1^{CK}$. This very surprising result gives answers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994).
No associations
LandOfFree
Wadge Degrees of Infinitary Rational Relations 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 Wadge Degrees of Infinitary Rational Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wadge Degrees of Infinitary Rational Relations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-36357