Classes of languages generated by the Kleene star of a word (Q1784949): Difference between revisions

Let \(\mathcal{U}\) be the class of all Kleene stars \(u^*\) of languages consisting of a single word \(u\). The authors study four classes of regular languages obtained as the closures of \(\mathcal{U}\) under various sets of language operations. These are the closure \(\mathcal{L}\) under the lattice operations union and intersection, the closure \(\mathcal{B}\) under the Boolean operations union, intersection and complement, the closure \(\mathcal{L}q\) under the lattice operations and quotients, and the closure \(\mathcal{B}q\) under the Boolean operations and quotients. The classes are not varieties of languages as defined by \textit{S. Eilenberg} [Automata, languages, and machines. Vol. B. New York-San Francisco-London: Academic Press (1976; Zbl 0359.94067)], but they are examples of the kinds of more general equationally definable classes of regular languages considered by \textit{M. Gehrke} et al. [Lect. Notes Comput. Sci. 5126, 246--257 (2008; Zbl 1165.68049)]. The authors characterize the classes \(\mathcal{L}\), \(\mathcal{B}\), \(\mathcal{L}q\) and \(\mathcal{B}q\) by profinite equations, and also present normal forms for each of the classes. They also show that using the equational characterizations one can decide whether a given regular language belongs to any one of the classes. These results apply to languages over alphabets with at least two letters, and the unary case is treated separately. Syntactic monoids are extensively used in this work.