English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that, from the topological point of view, 2-tape B\"uchi automatahave the same accepting power as Turing machines equipped with a B\"uchiacceptance condition. The Borel and the Wadge hierarchies of the classRAT_omega of infinitary rational relations accepted by 2-tape B\"uchi automataare equal to the Borel and the Wadge hierarchies of omega-languages accepted byreal-time B\"uchi 1-counter automata or by B\"uchi Turing machines. Inparticular, for every non-null recursive ordinal $\alpha$, there exist some$\Sigma^0_\alpha$-complete and some $\Pi^0_\alpha$-complete infinitary rationalrelations. And the supremum of the set of Borel ranks of infinitary rationalrelations is an ordinal $\gamma^1_2$ which is strictly greater than the firstnon-recursive ordinal $\omega_1^{CK}$. This very surprising result givesanswers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994).

Wadge Degrees of Infinitary Rational Relations