On alternating \(\omega\)-automata (Q1109572): Difference between revisions

The \(\omega\)-languages accepted by finite state deterministic and nondeterministic automata have been extensively studied under six natural acceptance conditions. The classes of \(\omega\)-languages accepted by alternating \(\omega\)-automata under four of these conditions were characterized by \textit{S. Miyano} and \textit{T. Hayashi} [Theor. Comput. Sci. 32, 321-330 (1984; Zbl 0544.68042)]. The paper considers the two remaining conditions C5 and C6: if \(M=(Q,f,\Sigma,\delta,q_ 0,\mathcal T)\) is an alternating finite state automaton, \(x\) an \(\omega\)-word, \(T(M,x)\) a computation tree of \(M\) on \(x\), \(\alpha\) a run in \(T(M,x)\), and \[ \begin{aligned} I(\alpha) &= \{q\in Q : q \text{ occurs in \(\alpha\) infinitely often}\},\\ O(\alpha) &= \{q\in Q : q \text{ occurs in }\alpha\}, \end{aligned} \] then C5 is \(I(\alpha)=F\), and C6 is \(O(\alpha)=F\), where \(F\) is some set from \(\mathcal T\), the family of designated sets. It is proved that the alternating \(\omega\)-automata accept precisely the \(\omega\)-regular languages under these conditions.