Wadge Degrees ofω-Languages of Deterministic Turing Machines
- 1 January 2003
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 37 (1) , 67-83
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 ξ = ω1 CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].Keywords
This publication has 9 references indexed in Scilit:
- Wadge Degrees of ω-Languages of Deterministic Turing Machines2003
- A hierarchy of deterministic context-free ω-languagesTheoretical Computer Science, 2003
- Fine hierarchy of regular ω-languagesTheoretical Computer Science, 1998
- ω-Languages1997
- Fine hierarchies and Boolean termsThe Journal of Symbolic Logic, 1995
- Fine hierarchy of regular ω-languages1995
- Hierearchies of hyperarithmetical sets and functionsAlgebra and Logic, 1983
- On ω-regular setsInformation and Control, 1979
- Wadge degrees and descriptive set theory1978