On alternating ω-automata

摘要

Deterministic and nondeterministic automata on ω-strings have been studied extensively under six different acceptance conditions. Miyano and Hayashi extended the study to alternating automata, but two of the conditions were not considered; the present paper completes the gap by showing that alternating ω-automata accept precisely the ω-regular languages under these conditions.