Alternation and ω-type Turing acceptors

AbstractWagner and Staiger (1977) characterized in the recursion-theoretic hierarchies the classes of ω-languages accepted by deterministic (D) and nondeterministic (N) ω-Turing acceptors under various acceptance conditions. In this paper their results are extended to alternating (A) ω-Turing acceptors. It is shown that under a certain acceptance condition alternating ω-Turing acceptors accept precisely the arithmetical ω-languages. On the other hand, the class of ω-languages accepted by alternating ω-Turing acceptors under Muller's condition lies properly between Σ11 and Δ12 in the analytical hierarchy. In terms of acceptional power each of the following situations is possible, depending on the acceptance condition chosen: D = N = A, D < N = A, D = N < A, and D < N < A