Wadge degrees of ω -languages of deterministic Turing machines

Victor Selivanov

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

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

Abstract

top
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].

How to cite

top

Selivanov, Victor. "Wadge degrees of $\sf \omega $-languages of deterministic Turing machines." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.1 (2003): 67-83. <http://eudml.org/doc/244653>.

@article{Selivanov2003,
abstract = {We describe Wadge degrees of $\omega $-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is $\xi ^\omega $ where $\xi =\omega ^\{\rm CK\}_1$ 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 - Informatique Théorique et Applications},
keywords = {hierarchy; Wadge degree; $\omega $-language; ordinal; Turing machine; set-theoretic operation; -language; Borel set; Wadge hierarchy},
language = {eng},
number = {1},
pages = {67-83},
publisher = {EDP-Sciences},
title = {Wadge degrees of $\sf \omega $-languages of deterministic Turing machines},
url = {http://eudml.org/doc/244653},
volume = {37},
year = {2003},
}

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
PB - EDP-Sciences
VL - 37
IS - 1
SP - 67
EP - 83
AB - We describe Wadge degrees of $\omega $-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is $\xi ^\omega $ where $\xi =\omega ^{\rm CK}_1$ 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; $\omega $-language; ordinal; Turing machine; set-theoretic operation; -language; Borel set; Wadge hierarchy
UR - http://eudml.org/doc/244653
ER -

References

top
  1. [1] A. Andretta, Notes on Descriptive Set Theory. Manuscript (2001). 
  2. [2] J. Duparc, A hierarchy of deterministic context-free ω -languages. Theoret. Comput. Sci. 290 (2003) 1253-1300. Zbl1044.68090MR1937723
  3. [3] Yu.L. Ershov, On a hierarchy of sets II. Algebra and Logic 7 (1968) 15-47 (Russian). Zbl0216.00902MR270912
  4. [4] 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). 
  5. [5] K. Kuratowski and A. Mostowski, Set Theory. North Holland, Amsterdam (1967). Zbl0165.01701MR229526
  6. [6] A. Louveau, Some results in the Wadge hierarchy of Borel sets. Springer, Lecture Notes in Math. 1019 (1983) 28-55. Zbl0535.03026MR730585
  7. [7] Y.N. Moschovakis, Descriptive set theory. North Holland, Amsterdam (1980). Zbl0433.03025MR561709
  8. [8] H. Rogers Jr., Theory of recursive functions and effective computability. McGraw-Hill, New York (1967). Zbl0183.01401MR224462
  9. [9] V.L. Selivanov, Hierarchies of hyperarithmetical sets and functions. Algebra i Logika 22 (1983) 666-692 (English translation: Algebra and Logic 22 (1983) 473-491). Zbl0548.03022MR781399
  10. [10] V.L. Selivanov, Hierarchies, Numerations, Index Sets. Handwritten Notes (1992) 300 pp. 
  11. [11] V.L. Selivanov, Fine hierarchy of regular ω -languages, Preprint No. 14. The University of Heidelberg, Chair of Mathematical Logic (1994) 13 pp. MR1490562
  12. [12] V.L. Selivanov, Fine hierarchy of regular ω -languages. Springer, Berlin, Lecture Notes in Comput. Sci. 915 (1995) 277-287. 
  13. [13] V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic 60 (1995) 289-317. Zbl0824.03022MR1324514
  14. [14] V.L. Selivanov, Fine hierarchy of regular ω -languages. Theoret. Comput. Sci. 191 (1998) 37-59. Zbl0908.68085MR1490562
  15. [15] V.L. Selivanov, Wadge Degrees of ω -Languages of Deterministic Turing Machines. Springer, Berlin, Lecture Notes in Comput. Sci. 2607 (2003) 97-108. Zbl1036.03033MR2066584
  16. [16] L. Staiger, ω -languages. Springer, Berlin, Handb. Formal Languages 3 (1997) 339-387. MR1470023
  17. [17] J. Steel, Determinateness and the separation property. J. Symb. Logic 45 (1980) 143-146. Zbl0487.03031MR604876
  18. [18] W. Wadge, Degrees of complexity of subsets of the Baire space. Notices Amer. Math. Soc. (1972) R-714. 
  19. [19] W. Wadge, Reducibility and determinateness in the Baire space, Ph.D. Thesis. University of California, Berkeley (1984). 
  20. [20] K. Wagner, On ω -regular sets. Inform. and Control 43 (1979) 123-177. Zbl0434.68061MR553694
  21. [21] R. Van Wesep, Wadge degrees and descriptive set theory. Springer, Lecture Notes in Math. 689 (1978) 151-170. Zbl0393.03037MR526917

NotesEmbed ?

top

You must be logged in to post comments.