Voir la notice de l'article provenant de la source Numdam
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 is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [2].
@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://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 :