Finite-state \(\omega\)-languages. (English) Zbl 0541.68052

This is an important paper about the basics of sets of infinite sequences of words, customarily referred to as \(\omega\)-languages. In particular, the paper is a contribution to the theory of finite-state \(\omega\)- languages introduced by B. A. Trakhtenbrot [Sib. Math. Zh. 3, 103- 131 (1962; Zbl 0115.007)]. The paper under review discusses the problem to what extent the class of finite-state \(\omega\)-languages and the class of regular \(\omega\)-languages coincide. The earlier investigations along these lines [e.g., M. Linna, Inf. Control 31, 272-293 (1976; Zbl 0329.68066)] have shown that the restriction of computational power is not successful to topological considerations, estimating the exact borderline in the Borel hierarchy between the ranges where all finite-state \(\omega\)-languages are regular and where not. To this end, some general properties of both regular and finite-state \(\omega\)-languages are established. As a by-result a partial solution to the minimization problem for finite automata accepting regular \(\omega\)-languages is obtained.
Reviewer: A.Salomaa


68Q45 Formal languages and automata
Full Text: DOI


[1] Brzozowski, J. A., Derivatives of regular expressions, J. Assoc. Comput. Mach., 11, 4, 481-494 (1964) · Zbl 0225.94044
[2] Buchi, J. R., On a decision method in restricted second order arithmetic, (Proceedings, 1960 Int. Congr. for Logic (1962), Stanford Univ. Press: Stanford Univ. Press Stanford), 1-11 · Zbl 0215.32401
[3] Bochi, J. R.; Landweber, L. H., Definability in the monadic second-order theory of successor, J. Symbolic Logic, 34, 2, 166-170 (1969) · Zbl 0209.02203
[4] Choueka, Y., Theories of automata on ω-tapes. A simplified approach, J. Comput. System Sci., 8, 117-141 (1974) · Zbl 0292.02033
[5] Cohen, R. S.; Gold, A. Y., Theory of ω-languages. I, II, J. Comput. System Sci., 15, 169-208 (1977) · Zbl 0363.68113
[6] Cohen, R. S.; Gold, A. Y., ω-Computations on deterministic pushdown machines, J. Comput. System Sci., 16, 257-300 (1978) · Zbl 0382.03025
[7] Kuratowski, K., Topology I (1974), Academic Press: Academic Press New York · Zbl 0274.54007
[8] Lindner, R.; Staiger, L., Algebraische Codierungstheorie-Theoree der sequentiellen Codierungen (1977), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0363.94016
[9] Linna, M., On cu-sets associated with context-free languages, Inform. and Control, 31, 273-293 (1976) · Zbl 0329.68066
[10] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and Control, 9, 521-530 (1966) · Zbl 0212.33902
[11] Salomaa, A., Theory of Automata (1969), Pergamon: Pergamon Oxford · Zbl 0193.32901
[12] Staiger, L., Zur Topologie der regulären Mengen (1976), Diss. A., Friedrich-Schiller-Universität: Diss. A., Friedrich-Schiller-Universität Jena
[13] Staiger, L., Regulare Nullmengen, Elektron. Informationsverarb. Kybernet., 12, 6, 307-311 (1976) · Zbl 0345.94030
[14] Staiger, L., A note on connected ω-languages, Elektron. Info rmationsverarb. Kybernet., 16, 5-6, 245-251 (1980) · Zbl 0452.68085
[15] Staiger, L.; Wagner, K., Automatentheoretische and automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen, Elektron. Informationsverarb. Kybernet., 10, 4, 379-392 (1974) · Zbl 0301.94069
[16] Trachtenbrot, B. A., Finite automata and the logic of one-place predicates, Siberian Math. J., 3, 1, 103-131 (1962), [Russian] · Zbl 0115.00701
[17] Wagner, K., On ω-regular sets, Inform. and Control, 43, 123-177 (1979) · Zbl 0434.68061
[18] Jurgensen, H.; Thierrin, G., On ω-Languages whose syntactic monoid is trivial (1982), Inst. Theoret. Informatik: Inst. Theoret. Informatik TH Darmstadt, Bericht TI-6/82 · Zbl 0545.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.