Geodesic
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 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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
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},
     pages = {67--83},
     year = {2003},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {1},
     doi = {10.1051/ita:2003008},
     mrnumber = {1991752},
     zbl = {1048.03031},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :