Classes of languages generated by the Kleene star of a word (Q1784949)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classes of languages generated by the Kleene star of a word |
scientific article |
Statements
Classes of languages generated by the Kleene star of a word (English)
0 references
27 September 2018
0 references
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.
0 references
regular language
0 references
finite automaton
0 references
Kleene star
0 references
profinite equation
0 references
syntactic monoid
0 references
decidability
0 references
0 references