Wadge Degrees of ω-Languages of Deterministic Turing Machines

Victor Selivanov

RAIRO - Theoretical Informatics and Applications (2010)

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

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.