# Wadge Degrees of ω-Languages of Deterministic Turing Machines

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 37, Issue: 1, page 67-83
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSelivanov, Victor. "Wadge Degrees of ω-Languages of Deterministic Turing Machines." RAIRO - Theoretical Informatics and Applications 37.1 (2010): 67-83. <http://eudml.org/doc/92714>.

@article{Selivanov2010,

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 [2].
},

author = {Selivanov, Victor},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Hierarchy; Wadge degree; ω-language; ordinal; Turing machine;
set-theoretic operation.; -language; Borel set; Wadge hierarchy},

language = {eng},

month = {3},

number = {1},

pages = {67-83},

publisher = {EDP Sciences},

title = {Wadge Degrees of ω-Languages of Deterministic Turing Machines},

url = {http://eudml.org/doc/92714},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Selivanov, Victor

TI - Wadge Degrees of ω-Languages of Deterministic Turing Machines

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 1

SP - 67

EP - 83

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 [2].

LA - eng

KW - Hierarchy; Wadge degree; ω-language; ordinal; Turing machine;
set-theoretic operation.; -language; Borel set; Wadge hierarchy

UR - http://eudml.org/doc/92714

ER -

## References

top- A. Andretta, Notes on Descriptive Set Theory. Manuscript (2001).
- J. Duparc, A hierarchy of deterministic context-free ω-languages. Theoret. Comput. Sci.290 (2003) 1253-1300.
- Yu.L. Ershov, On a hierarchy of sets II. Algebra and Logic7 (1968) 15-47 (Russian).
- 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).
- K. Kuratowski and A. Mostowski, Set Theory. North Holland, Amsterdam (1967).
- A. Louveau, Some results in the Wadge hierarchy of Borel sets. Springer, Lecture Notes in Math. 1019 (1983) 28-55.
- Y.N. Moschovakis, Descriptive set theory. North Holland, Amsterdam (1980).
- H. Rogers Jr., Theory of recursive functions and effective computability. McGraw-Hill, New York (1967).
- V.L. Selivanov, Hierarchies of hyperarithmetical sets and functions. Algebra i Logika22 (1983) 666-692 (English translation: Algebra and Logic 22 (1983) 473-491).
- V.L. Selivanov, Hierarchies, Numerations, Index Sets. Handwritten Notes (1992) 300 pp.
- V.L. Selivanov, Fine hierarchy of regular ω-languages, Preprint No. 14. The University of Heidelberg, Chair of Mathematical Logic (1994) 13 pp.
- V.L. Selivanov, Fine hierarchy of regular ω-languages. Springer, Berlin, Lecture Notes in Comput. Sci. 915 (1995) 277-287.
- V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic60 (1995) 289-317.
- V.L. Selivanov, Fine hierarchy of regular ω-languages. Theoret. Comput. Sci.191 (1998) 37-59.
- V.L. Selivanov, Wadge Degrees of ω-Languages of Deterministic Turing Machines. Springer, Berlin, Lecture Notes in Comput. Sci. 2607 (2003) 97-108.
- L. Staiger, ω-languages. Springer, Berlin, Handb. Formal Languages 3 (1997) 339-387.
- J. Steel, Determinateness and the separation property. J. Symb. Logic45 (1980) 143-146.
- W. Wadge, Degrees of complexity of subsets of the Baire space. Notices Amer. Math. Soc. (1972) R-714.
- W. Wadge, Reducibility and determinateness in the Baire space, Ph.D. Thesis. University of California, Berkeley (1984).
- K. Wagner, On ω-regular sets. Inform. and Control43 (1979) 123-177.
- R. Van Wesep, Wadge degrees and descriptive set theory. Springer, Lecture Notes in Math. 689 (1978) 151-170.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.