On generators of rational \(\omega\)-power languages. (English) Zbl 0632.68080

An \(\omega\)-power of a language L is the set \(L^{\omega}\) of all semi- infinite concatenations \(w_ 1\cdot w_ 2\cdot..\). of nonempty words \(w_ i\in L\). The authors study for a given regular (rational) \(\omega\)- language F the set of its generators \(\{\) \(L: L^{\omega}=F\}\). They show that it is decidable for a regular \(\omega\)-language F whether it is the \(\omega\)-power of some language L and that in case \(F=L^{\omega}\) there is also a regular language R such that \(F=R^{\omega}\). Moreover, it is shown that for every regular \(\omega\)-power F the set \(\{\) \(L: L^{\omega}=F\}\) of its generators has a finite number of maximal elements each of which is regular, and any generator L of F is contained in some of these maximal generators.
Then the authors turn to minimal generators of a regular \(\omega\)-power \(L^{\omega}\), and they show that also the property to be a minimal generator of the \(\omega\)-language \(L^{\omega}\) is decidable for the regular language L. But in contrast to the case of maximal generators, there are minimal generators of regular \(\omega\)-powers which are not regular. The following example settles this problem still open in the paper under review.
Example. \(F=(b\cdot a^*)^{\omega}\) has the minimal generator \(L:=\cup^{\infty}_{i=0}b\cdot a^ i\cdot (b\cdot a^*)^ i\) which is, obviously, not regular.
Reviewer: L.Staiger


68Q45 Formal languages and automata
Full Text: DOI


[1] Arnold, A., A syntactic congruence for rational ω-languages, Theoret. Comput. Sci., 39, 333-335 (1985) · Zbl 0578.68057
[2] Berstel, J., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 0587.68066
[3] Doasson, L.; Nivat, M., Adherences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[4] Büchi, J., On a decision method in restricted second order arithmetic, (Proc. Internat. Cong. Logic, Methodology and Philosophy (1960), Stanford Univ. Press), 1-11 · Zbl 0147.25103
[5] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[6] Latteux, M.; Timmerman, E., Finitely generated \(ω\)-languages, Inform. Process. Lett., 23, 171-175 (1986) · Zbl 0627.68059
[7] Le Saec, B., Automates à cycles et automates des facteurs gauches, (Technical Report No. 8531, 1 (1985), Univ. de Bordeaux)
[8] MacNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and Control, 9, 521-530 (1966) · Zbl 0212.33902
[9] Nivat, M., Sur les ensembles de mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor., 12, 259-278 (1978) · Zbl 0387.68050
[10] Perrin, D., An introduction to finite automata of infinite words, (Nivat, M.; Perrin, D., Automata on Infinite words. Automata on Infinite words, Lecture Notes in Computer Science, 192 (1985), Springer: Springer Berlin), 2-17 · Zbl 0604.68091
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.