Wadge Degrees of Infinitary Rational Relations
Olivier Finkel · 2008
We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as Turing machines equipped with a Büchi acceptance condition. The Borel and the Wadge hierarchies of the class RATω of infinitary rational relations accepted by 2-tape Büchi automata are equal to the Borel and the Wadge hierarchies of ω-languages accepted by realtime Büchi 1-counter automata or by Büchi Turing machines. In particular, for every non null recursive ordinal α, there exist some Σ 0 α-complete and some Π 0 α-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal γ 1 2 which is strictly greater than the first non recursive ordinal ω CK 1. This very surprising result gives answers to questions of Simonnet [Sim92] and of Lescow and Thomas [Tho88, LT94].