Research in the theory of \(\omega\)-languages. (English) Zbl 0637.68095

Staiger, Ludwig

J. Inf. Process. Cybern. 23, 415-439 (1987).

The subject of automata on infinite sequences was established in the early sixties mainly motivated by the investigation of decision problems in mathematical logic. From this core the theory has developed into numerous directions. In the last time the theory of \(\omega\)-languages became popular, several papers and books survey in a more or less complete manner some part of this theory. Among these the present paper tries not only to survey recent results, but also goes back to the seventies.
The topics on which this survey focuses are the following ones: (1) Acceptance types and topology, (2) Operations for \(\omega\)-languages, (3) Complexity of acceptance, (4) Finite-state \(\omega\)-languages, (5) Systems of equations and formal proof systems for \(\omega\)-regular expressions. The paper is provided with an extensive list of references containing 117 items.
The author intends to present the first two topics as a systematic treatise of the connections between acceptance types and topology for the classes of \(\omega\)-languages accepted by finite automata, Turing machines and pushdown automata as well as the representation of these classes using the corresponding families of languages and operations on them.
The remaining three topics are not equally extensively treated. Topic 3 contains a brief account on K. Wagner’s paper [Inf. Control 43, 123-177 (1979; Zbl 0434.68061)] and its relation to other results. The next topic deals with the peculiarities of the \(\omega\)-languages having a finite syntactic monoid which is applied in the last topic to the study of systems of linear equations for \(\omega\)-languages accepted by finite automata.

Reviewer: L.Staiger

MSC:

68Q45	Formal languages and automata
03D05	Automata and formal grammars in connection with logical questions

Keywords:

Borel hierarchy; bibliography; \(\omega \)-languages; survey; finite automata; Turing machines; pushdown automata

Citations:

Zbl 0434.68061