Variétés de langages formels. Préface du M. P. Schützenberger. (French) Zbl 0636.68093

Pin, J. E.

Études et Recherches en Informatique. Paris etc.: Masson. 160 p. (1984).

La notion de variété de langage - qui figure dans le title - a été introduite en 1976 par Eilenberg. Elle a permis de formaliser l’approche entre les automates, langages et semigroupes et a fourni un cadre unifié à la théorie.
L’A. du présente livre est bien connu par les importants travaux sur les variétés de langages. Ce livre présente les résultats fondamentaux de la théorie des automates et des langages reconnaissables - ou langages réguliers.
Une interessante préface, signée par M. P. Schützenberger, montre l’importance des automates finis et des langages rationnels pour l’informatique théorique et met en evidence les qualités du présent livre de J. E. Pin: “C’est donc un ouvrage autonome, à la fois d’initiation et de préparation à la recherche, que l’A. présente au public mathématique et informatique”.
Passons rapidement en revue le contenu de livre.
Le chapitre 0 est purement introductif. Il contient les notations utilisées dans ce livre.
Dans le chapitre 1 sont donnés les définitions relatives aux semigroupes et aux langages qui sont utilisées par la suite. La seconde section de chapitre résume les liens entre les automates, semigroupes et langages. La dernière partie est consacrée au calcul explicite de deux semigroupes syntactiques.
Le chapitre 2 est dédié aux variétés. Dans la première section sont définies les variétés de semigroupes et de monoïdes finis. On donne leur interprétation en termes d’équations. On démontre le théorème des variétés d’Eilenberg. La dernière section du chapitre présente quelques exemples classiques de variétés de langages.
Le troisième chapitre est un introduction à la théorie classique des semigroupes finis. On y présente: relations de Green, structures de \({\mathcal V}\)-classes réguliers et structure de l’ideal minimal d’un semigroupe fini. Dans la dernière section sont présentés les variétés de semigroupes, définiés par les relations de Green et on introduit les morphismes relationnels et les \({\mathcal V}\)-morphismes.
Dans le chapitre 4 sont démontrés deux théorèmes fondamentaux de la théorie des variétés de langages: le théorème de I. Simon sur les langages testables par morceaux et le théorème de Schützenberger sur les langages sans étoile. On y trouve des applications du théorème de Simon aux semigroupes finis et la caractérisations des langages, \({\mathcal R}\)-triviaux et \({\mathcal L}\)- triviaux.
Dans le dernière chapitre sont présentés sans démonstrations les principaux résultats et problèmes ouverts concernant les variétés de langage.
Le livre est intéressant. On présent les résultats classiques sous leur forme moderne. Pour aider le lecteur, le livre contient un grand nombre d’exemples. En même temps chaque chapitre est complété par une série de problèmes. La bibliographie est riche, contenant de brefs commentaires pour un grand nombre de livres et d’articles, destinés à faciliter l’orientation du lecteur. Cet ouvrage est écrit d’une mani‘ere tres claire et ne necessité aucune connaissance antérieur sur les langages formels ou les automates. Sa lecture peut être abordée avec un minimum de connaissances mathématiques. Ce livre répresant une contribution remarquable dans la littératur destinée aux variétés de langages et sera très utile aux informaticiens et aux mathématiciens, étudiants et chercheurs, intéresses par les problèmes théorique issus de l’informatique. [For the review of the English edition (Plenum, New York 1986) see Zbl 0632.68069.]

Reviewer: C.V.Craciun

MSC:

68Q45	Formal languages and automata
68-02	Research exposition (monographs, survey articles) pertaining to computer science
20M35	Semigroups in automata theory, linguistics, etc.
20M05	Free semigroups, generators and relations, word problems
68Q70	Algebraic theory of languages and automata
20M07	Varieties and pseudovarieties of semigroups

Keywords:

finite automata; regular languages; varieties of languages; varieties of semigroups; finite monoids; Green relations; hierarchies; bibliography

Citations:

Zbl 0632.68069