Wadge Degrees of Infinitary Rational Relations

Abstract

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_omega of infinitary rational relations accepted by 2-tape Büchi automata are equal to the Borel and the Wadge hierarchies of omega-languages accepted by real-time Büchi 1-counter automata or by Büchi Turing machines. In particular, for every non-null recursive ordinal $\alpha$, there exist some ${\Sigma }_{\alpha }^0$-complete and some ${\Pi }_{\alpha }^0$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal ${\gamma }_2^1$ 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).

to appear in the journal Mathematics in Computer Science, in a Special Issue on Intensional Programming & Semantics, in honour of Bill Wadge on the occasion of his 60th cycle