DOI

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.
Original languageEnglish
Title of host publicationSTACS 2003 (STACS 2003)
Pages97-108
Number of pages12
DOIs
StatePublished - 1 Jan 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume2607
ISSN (Print)0302-9743

    Research areas

  • Cantor space, Hierarchy, Reducibility, Set-theoretic operation, Wadge degree, ω-language

ID: 127140800