Séminaire Lotharingien de Combinatoire, B06j (1982), 13 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1982, 191/S-05, p.
85-97.]
Jean-Éric Pin
Varietés de langages et combinatoire
Abstract.
Let A be a finite alphabet.
The well-known Kleene's theorem states that a language L of A*
is rational iff its syntactic monoid is finite. Schützenberger's
theorem states that a language L is star-free iff its syntactic
monoid is group-free. It turns out that many subfamilies of the rational
languages can be characterized in this way by properties of their
syntactic monoids or semigroups. This lecture gives a survey of the
various hierarchies of star-free languages, their descriptions in
terms of semigroups, and the related decidability results and problems.
The following version is available: