Accepting conditions for automata on \(\omega\)-languages (Q1116351): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(88)90121-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2002992825 / rank | |||
Normal rank |
Revision as of 22:25, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Accepting conditions for automata on \(\omega\)-languages |
scientific article |
Statements
Accepting conditions for automata on \(\omega\)-languages (English)
0 references
1988
0 references
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.
0 references
acceptance
0 references
finite automata
0 references
regular \(\omega\)-languages
0 references