On generators of rational \(\omega\)-power languages (Q1095674)

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.