Classes of languages generated by the Kleene star of a word
type: Item
instance of: scholarly article
title: Classes of languages generated by the Kleene star of a word
zbMATH Open document ID: 1408.68097
author: Laure Daviaud
author: Charles Paperman
published in: Information and Computation
publication date: 2018-09-27T00:00:00Z
full work available at URL: main.pdf
review text: 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.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6944934
zbMATH Keywords: regular language
zbMATH Keywords: finite automaton
zbMATH Keywords: Kleene star
zbMATH Keywords: profinite equation
zbMATH Keywords: syntactic monoid
zbMATH Keywords: decidability
MaRDI profile type: Publication
OpenAlex ID: W2143540670
cites work: PROFINITE IDENTITIES FOR FINITE SEMIGROUPS WHOSE SUBGROUPS BELONG TO A GIVEN PSEUDOVARIETY
cites work: Q3123634
cites work: Classes of Languages Generated by the Kleene Star of a Word
cites work: On pseudovarieties
cites work: Duality and Equational Theory of Regular Languages
cites work: Q4790421
cites work: Q4341774
cites work: Q5641083
cites work: Profinite Methods in Automata Theory
cites work: Some results on the generalized star-height problem
cites work: Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands
cites work: The Birkhoff theorem for finite algebras
cites work: On finite monoids having only trivial subgroups
cites work: Q4714446
DOI: 10.1016/J.IC.2018.07.002
Recommended article: Duality and Equational Theory of Regular Languages
Recommended article: EQUATIONAL DESCRIPTIONS OF LANGUAGES
Recommended article: Faithful Loops for Aperiodic E-Ordered Monoids
Recommended article: Q3044353
Recommended article: Duality and the equational theory of regular languages.
Recommended article: Q5740411
Recommended article: Classes of Languages Generated by the Kleene Star of a Word
Recommended article: Q4407423
Recommended article: Q4453870
Recommended article: Q3769981
description: scientific article; zbMATH DE number 6944934