Wadge degrees of ω-languages of deterministic Turing machines
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 67-83.

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

DOI : 10.1051/ita:2003008
Classification : 03D55, 04A15, 68Q05
Mots-clés : 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},
     pages = {67--83},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {1},
     year = {2003},
     doi = {10.1051/ita:2003008},
     mrnumber = {1991752},
     zbl = {1048.03031},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003008/}
}
TY  - JOUR
AU  - Selivanov, Victor
TI  - Wadge degrees of $\sf \omega $-languages of deterministic Turing machines
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2003
SP  - 67
EP  - 83
VL  - 37
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003008/
DO  - 10.1051/ita:2003008
LA  - en
ID  - ITA_2003__37_1_67_0
ER  - 
%0 Journal Article
%A Selivanov, Victor
%T Wadge degrees of $\sf \omega $-languages of deterministic Turing machines
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2003
%P 67-83
%V 37
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2003008/
%R 10.1051/ita:2003008
%G en
%F 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, Tome 37 (2003) no. 1, pp. 67-83. doi : 10.1051/ita:2003008. http://www.numdam.org/articles/10.1051/ita:2003008/

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

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

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

[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 | Zbl

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

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

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

[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 | Zbl

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

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

[12] V.L. Selivanov, Fine hierarchy of regular ω-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 | Zbl

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

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

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

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

[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 ω-regular sets. Inform. and Control 43 (1979) 123-177. | MR | Zbl

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

Cité par Sources :