Varieties of formal languages. Transl. from the French by A. Howie. (English) Zbl 0632.68069

Foundations of Computer Science. New York: Plenum Publishing Corporation. X, 138 p. (1986).
The book is a synthesis of (mainly) recent results concerning finite automata and regular languages from the point of view of varieties of languages. “This approach has at least two advantages: it enables us to handle classical results in a concise and rigorous manner, and it facilitates access to the most recent results and problems” (from the foreword). As the author explicitly says, “the book should enable the reader to arrive quickly at the research level”. It starts by giving all basic definitions and ends with a chapter which presents (without proofs) many recent results of the theory (as well as open problems).
Besides the preface (by M. P. Schützenberger), the foreword, an introduction with mathematical prerequisites, bibliographical notes (basic references with comments, specialized articles, surveys) and an index of notions, the book contains five chapters. The first one (Semigroups, languages and automata) presents the basic notions investigated in the rest of the book: free semigroups, languages, finite automata, regular/\(recognizable/rational\) languages, syntactic monoid (including algorithms for computing it). Chapter 2 (Varieties) presents the varieties of semigroups and of finite monoids, equations of a variety and the Eilenberg variety theorem.
Chapter 3 (Structure of finite semigroups) deals with Green relations, Rees semigroups, varieties defined by Green relations. Chapter 4 (Piecewise-testable languages and star-free languages) proves Simon’s theorem about piecewise-testable languages and Schützenberger’s theorem about star-free languages. Among the topics dealt with in the last chapter, we quote: operations on languages, monoids and varieties (concatenation, star, shuffle, substitution, etc.), locally testable languages, the hierarchies of Straubing and of Brzozowski, relations with the theory of codes, the lattice of varieties, etc.
A rigorous, quite polished work, including many notions, results, exercises, at the level of an advanced graduate course (actually used by the author for a course at the University of Paris VI).
Reviewer: Gh.Păun


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