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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.