Varietés de langages et combinatoire
Séminaire lotharingien de combinatoire, Tome 06 (1982)
Citer cet article
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
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.