Wadge degrees of $\omega$-languages of deterministic Turing machines
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 37 (2003) no. 1, p. 67-83

We describe Wadge degrees of $\omega$-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ${\xi }^{\omega }$ where $\xi ={\omega }_{1}^{\mathrm{CK}}$ is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [2].

DOI : https://doi.org/10.1051/ita:2003008
Classification:  03D55,  04A15,  68Q05
Keywords: hierarchy, Wadge degree, $\omega$-language, ordinal, Turing machine, set-theoretic operation
@article{ITA_2003__37_1_67_0,
author = {Selivanov, Victor},
title = {Wadge degrees of $\sf \omega$-languages of deterministic Turing machines},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
pages = {67-83},
doi = {10.1051/ita:2003008},
zbl = {1048.03031},
mrnumber = {1991752},
language = {en},
url = {http://www.numdam.org/item/ITA_2003__37_1_67_0}
}

Selivanov, Victor. Wadge degrees of $\sf \omega$-languages of deterministic Turing machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 37 (2003) no. 1, pp. 67-83. doi : 10.1051/ita:2003008. http://www.numdam.org/item/ITA_2003__37_1_67_0/

[1] A. Andretta, Notes on Descriptive Set Theory. Manuscript (2001).

[2] J. Duparc, A hierarchy of deterministic context-free $\omega$-languages. Theoret. Comput. Sci. 290 (2003) 1253-1300. | MR 1937723 | Zbl 1044.68090

[3] Yu.L. Ershov, On a hierarchy of sets II. Algebra and Logic 7 (1968) 15-47 (Russian). | MR 270912 | Zbl 0216.00902

[4] J. Köbler, U. Shöning and K.W. Wagner, The difference and truth-table hierarchies for NP, Preprint 7. Dep. of Informatics, Koblenz (1986).

[5] K. Kuratowski and A. Mostowski, Set Theory. North Holland, Amsterdam (1967). | MR 229526 | Zbl 0165.01701

[6] A. Louveau, Some results in the Wadge hierarchy of Borel sets. Springer, Lecture Notes in Math. 1019 (1983) 28-55. | MR 730585 | Zbl 0535.03026

[7] Y.N. Moschovakis, Descriptive set theory. North Holland, Amsterdam (1980). | MR 561709 | Zbl 0433.03025

[8] H. Rogers Jr., Theory of recursive functions and effective computability. McGraw-Hill, New York (1967). | MR 224462 | Zbl 0183.01401

[9] V.L. Selivanov, Hierarchies of hyperarithmetical sets and functions. Algebra i Logika 22 (1983) 666-692 (English translation: Algebra and Logic 22 (1983) 473-491). | MR 781399 | Zbl 0548.03022

[10] V.L. Selivanov, Hierarchies, Numerations, Index Sets. Handwritten Notes (1992) 300 pp.

[11] V.L. Selivanov, Fine hierarchy of regular $\omega$-languages, Preprint No. 14. The University of Heidelberg, Chair of Mathematical Logic (1994) 13 pp. | MR 1490562

[12] V.L. Selivanov, Fine hierarchy of regular $\omega$-languages. Springer, Berlin, Lecture Notes in Comput. Sci. 915 (1995) 277-287.

[13] V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic 60 (1995) 289-317. | MR 1324514 | Zbl 0824.03022

[14] V.L. Selivanov, Fine hierarchy of regular $\omega$-languages. Theoret. Comput. Sci. 191 (1998) 37-59. | MR 1490562 | Zbl 0908.68085

[15] V.L. Selivanov, Wadge Degrees of $\omega$-Languages of Deterministic Turing Machines. Springer, Berlin, Lecture Notes in Comput. Sci. 2607 (2003) 97-108. | MR 2066584 | Zbl 1036.03033

[16] L. Staiger, $\omega$-languages. Springer, Berlin, Handb. Formal Languages 3 (1997) 339-387. | MR 1470023

[17] J. Steel, Determinateness and the separation property. J. Symb. Logic 45 (1980) 143-146. | MR 604876 | Zbl 0487.03031

[18] W. Wadge, Degrees of complexity of subsets of the Baire space. Notices Amer. Math. Soc. (1972) R-714.

[19] W. Wadge, Reducibility and determinateness in the Baire space, Ph.D. Thesis. University of California, Berkeley (1984).

[20] K. Wagner, On $\omega$-regular sets. Inform. and Control 43 (1979) 123-177. | MR 553694 | Zbl 0434.68061

[21] R. Van Wesep, Wadge degrees and descriptive set theory. Springer, Lecture Notes in Math. 689 (1978) 151-170. | MR 526917 | Zbl 0393.03037