Standard

Wadge degrees of ω-languages of deterministic turing machines. / Selivanov, Victor.

STACS 2003 (STACS 2003). 2003. p. 97-108 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2607).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Selivanov, V 2003, Wadge degrees of ω-languages of deterministic turing machines. in STACS 2003 (STACS 2003). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2607, pp. 97-108. https://doi.org/10.1007/3-540-36494-3_10

APA

Selivanov, V. (2003). Wadge degrees of ω-languages of deterministic turing machines. In STACS 2003 (STACS 2003) (pp. 97-108). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2607). https://doi.org/10.1007/3-540-36494-3_10

Vancouver

Selivanov V. Wadge degrees of ω-languages of deterministic turing machines. In STACS 2003 (STACS 2003). 2003. p. 97-108. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-36494-3_10

Author

Selivanov, Victor. / Wadge degrees of ω-languages of deterministic turing machines. STACS 2003 (STACS 2003). 2003. pp. 97-108 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{f5b6bbcfdf4a42709f50acc3fe135422,
title = "Wadge degrees of ω-languages of deterministic turing machines",
abstract = "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 ξ = ω1CK is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [Du0?]. {\textcopyright} Springer-Verlag Berlin Heidelberg 2003.",
keywords = "Cantor space, Hierarchy, Reducibility, Set-theoretic operation, Wadge degree, ω-language",
author = "Victor Selivanov",
year = "2003",
month = jan,
day = "1",
doi = "10.1007/3-540-36494-3_10",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "97--108",
booktitle = "STACS 2003 (STACS 2003)",

}

RIS

TY - GEN

T1 - Wadge degrees of ω-languages of deterministic turing machines

AU - Selivanov, Victor

PY - 2003/1/1

Y1 - 2003/1/1

N2 - 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 ξ = ω1CK is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [Du0?]. © Springer-Verlag Berlin Heidelberg 2003.

AB - 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 ξ = ω1CK is the first non-recursive ordinal known as the Church-Kleene ordinal. This answers a question raised in [Du0?]. © Springer-Verlag Berlin Heidelberg 2003.

KW - Cantor space

KW - Hierarchy

KW - Reducibility

KW - Set-theoretic operation

KW - Wadge degree

KW - ω-language

UR - http://www.scopus.com/inward/record.url?scp=33750688771&partnerID=8YFLogxK

U2 - 10.1007/3-540-36494-3_10

DO - 10.1007/3-540-36494-3_10

M3 - Conference contribution

AN - SCOPUS:33750688771

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 108

BT - STACS 2003 (STACS 2003)

ER -

ID: 127140800