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

Staiger, Ludwig

J. Comput. Syst. Sci. 27, 434-448 (1983).

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

MSC:

68Q45

Formal languages and automata

Keywords:

finite state omega-languages; regular omega-languages; infinite sequences of words; topological considerations; Borel hierarchy; minimization problem for finite automata

Citations:

Zbl 0115.007; Zbl 0329.68066

References:

[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