×

zbMATH — the first resource for mathematics

Finite semigroups and universal algebra. Rev. and transl. by the author. (English) Zbl 0844.20039
Series in Algebra 3. Singapore: World Scientific. (ISBN 981-02-1895-8). xvi, 511 p. (1994).
[For a review of the Portuguese original (São Paulo, 1992) see Zbl 0757.08001.]
Finite semigroups have been intensively investigated from the very beginning of semigroup theory. The modern trend in studying finite semigroups is based on what may be called the varietal approach in which one focuses on certain variety-like classes rather than individual semigroups. Such classes (called pseudovarieties or varieties of finite semigroups) were introduced by S. Eilenberg who has shown that the algebraic classification of formal languages inevitably leads to pseudovarieties [Automata, languages and machines, Vol. B (1976; Zbl 0359.94067)]. Semigroup pseudovarieties are also closely related with another important branch of theoretical computer science – the theory of finite automata. The book under review presents some important recent achievements in semigroup pseudovarieties.
The key point of the author’s approach is to consequently use ideas and methods originated in universal algebra. The fact that there exist reasonable pseudovarietal analogues of the main tools of the theory of (Birkhoff) varieties such as identities and free algebras was first discovered by J. Reiterman [Algebra Univers. 14, 1-10 (1982; Zbl 0484.08007)] but it was the author who systematically explored these analogues and made them really work for finite semigroup theory.
The book consists of 13 Chapters. Chapter 0 (Introduction) recalls the aforementioned motivation for the study of semigroup pseudovarieties. Chapters 1-4 form Part I of the book entitled “Finite Universal Algebra”. Chapters 1 and 2 introduce some basic concepts and results which are related to Birkhoff varieties, ordered sets and uniform spaces frequently used in studying pseudovarieties. Chapter 3 contains the fundamental results about pseudovarieties of arbitrary finite algebras. The crucial notions of a topological algebra of implicit operations and of a pseudoidentity appear here. Chapter 4 introduces certain algorithmic problems including the main problem of the theory of pseudovarieties, the membership problem, and discusses its relationship with the finite pseudoidentity basis property.
Chapter 5-12 form Part II, “Finite Semigroups and Monoids”. Chapter 5 contains some necessary preliminaries about semigroups and graphs. Chapters 6 and 8 contain a detailed study of, respectively, permutative pseudovarieties and pseudovarieties of semigroups whose regular \(\mathcal D\)-classes are subsemigroups. Chapter 7 studies the interrelations between pseudovarieties of semigroups and monoids. Chapters 9, 10 and 11 are basically devoted to the membership problem for pseudovarieties arising as the result of taking the lattice join or the semidirect product of two given pseudovarieties or applying the power operator to a given pseudovariety. Chapter 12 deals with factorizations of implicit operations.
The main text of the book concludes with a list of 60 research problems and with bibliographical notes for each chapter. Both the problems and the bibliographical notes are essentially updated for the English translation.
The book under review constitutes an important contribution to the most active part of the present theory of finite semigroups. An overwhelming majority of the results included in it is very new and has been scattered over journals so far. The book does not cover all of the theory of semigroup pseudovarieties (in fact, no book could do this just because the field is now developing too fast) but it is extremely rich in material and ideas presented with skill and dedication. The book has already influenced the area essentially, and its influence will certainly grow.
There are a few misprints and inaccurate formulations in the book, mostly harmless. I list here only those which might confuse a less experienced reader. The claim of Exercise 3.2.16 is wrong (in fact, there are uncountable chains and antichains even among pseudovarieties of abelian groups). A phrase on page 109 might be interpreted as saying that the word problem for one-relator monoid presentations is known to be decidable while it is still open. In the formulation of Theorem 6.1.20 the lattice \({\mathcal G}({\mathcal N}\text{il}\cap{\mathcal C}\text{om})\) should stand instead of the lattice \({\mathcal G}({\mathcal N}\text{il})\). In the proof of the Krohn-Rhodes theorem (pages 296-297) one should use the pseudovariety \({\mathbf M}{\mathbf K}_1\) rather than its dual \({\mathbf M}{\mathbf D}_1\).
As mentioned, the theory of semigroup pseudovarieties has been growing rapidly, and therefore, it is not a surprise that some of the research problems proposed in the book are solved now. In fact, the announced solutions of Problems 8, 15, 16 and 17 have been already footnoted in the book. Meanwhile the solution of Problem 8 appeared in the reviewer’s paper [Int. J. Algebra Comput. 5, 127-135 (1995; Zbl 0834.20058)], and the author and P. Weil’s paper “Free profinite \(\mathcal R\)-trivial monoids” containing the solution of Problem 15 will soon appear in the same journal. G. Churchill has announced that Problem 10 has a negative solution. A. Azevedo and M. Zeitoun answered all three questions of Problem 24: the answers are ‘Yes’ to question b) and ‘No’ to questions a) and c). Problem 29 (that asks whether the semidirect product of two pseudovarieties generated by a finite semigroup is again generated by a finite semigroup) can be easily answered in the negative. Indeed, consider the semidirect square \({\mathbf A}{\mathbf b}_p^2\) of the pseudovariety generated by the cyclic group of prime order \(p\). Then \({\mathbf A}{\mathbf b}_p^2\) contains nilpotent groups of any nilpotency class: for example, the group given by the presentation \(\langle x, y_1, \ldots, y_n \mid x^p = y_i^p = 1\;(1 \leq i \leq n)\), \(y_i y_j = y_j y_i\) \((1 \leq i < j \leq n)\), \(y_k^x = y_{k+1}\) \((1 \leq k < n)\), \(y_n^x = y_n \rangle\) is easily seen to belong to \({\mathbf A}{\mathbf b}_p^2\) and to have the nilpotency class \(n\). However, the nilpotency class of any group in a pseudovariety generated by a finite semigroup \(S\) cannot exceed the maximum of the nilpotency classes of nilpotent subgroups of \(S\). Therefore the pseudovariety \({\mathbf A}{\mathbf b}_p^2\) cannot be generated by a finite semigroup. L. Teixeira has shown that the conjecture in Problem 31 is false; the problem itself still remains open. P. G. Trotter has announced an example answering Problem 41 in the negative.
It is worth mentioning an interesting feature of the book under review – it was basically translated from the Portuguese by a computer program written in Prolog by M. Filgueiras, see his report [A successful case of Computer Aided Translation, Proc. 4th Conf. on Applied Natural Language Processing, M. Kauffman (ed.), 91-94 (1994)]. The program (running on a MIPS computer) converted the whole TEX-file of the Portuguese original into the English TEX-file (which then has been edited by hand) in a little over 2 minutes.
I think the book is a must for researchers in the area but it is also very useful for all those who want to trace modern developments in the theory of semigroups.

MSC:
20M07 Varieties and pseudovarieties of semigroups
20-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to group theory
20-02 Research exposition (monographs, survey articles) pertaining to group theory
08B15 Lattices of varieties
20M05 Free semigroups, generators and relations, word problems
08-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to general algebraic systems
08C15 Quasivarieties
20M35 Semigroups in automata theory, linguistics, etc.
PDF BibTeX XML Cite