Accepting conditions for automata on \(\omega\)-languages (Q1116351): Difference between revisions

Two new acceptance conditions for \(\omega\)-automata are introduced: An \(\omega\)-word \(\beta\) is L-accepted (L'-accepted) by the automaton \({\mathfrak A}\) if and only if the automaton \({\mathfrak A}\) enters (does not enter, respectively) on its (some of its if A is nondeterministic) run on \(\beta\) all of its accepting states infinitely often. The corresponding classes L, L', \({\mathcal N}L\), and \({\mathcal N}L'\) of \(\omega\)-languages L- or L'-accepted by deterministic or nondeterministic finite automata are investigated in detail. It turns out that they are pairwise distinct and, moreover, none of them coincides with some of the well-known classes of regular \(\omega\)- languages introduced by \textit{L. H. Landweber} [Math. Syst. Theory 3, 376- 384 (1969; Zbl 0182.024)] and the reviewer and \textit{K. Wagner} [Elektron. Informationsverarbeitung Kybernetik 10, 379-392 (1974; Zbl 0301.94069)]. The investigations are completed by presenting all inclusions between the classes L, L', \({\mathcal N}L\), \({\mathcal N}L'\) and the previously known classes of regular \(\omega\)-languages.