Semigroups and combinatorial applications

Review: SEMIGROUPS AND COMBINATORIAL APPLICATIONS By G. LALLEMENT: pp. 376. £16-75. (Wiley-Interscience, 1979.) A book with 'Semigroups' in the title can be about a number of widely different topics, there being little in common between (say) Hille and Phillips's Functional analysis and semigroups [4] and Clifford and Preston's The algebraic theory of semigroups [1]. Lallement's book, having only a little more in common with the latter than with the former, is a valuable new contribution to the rapidly growing set of books in this area. Its main 'rival' would appear to be Eilenberg's Automata, languages and machines [2], since most of the combinatorial applications referred to in the title are in the area covered by Eilenberg's volumes, but the approach is more semigroup-centred than Eilenberg's, and the exposition lacks the majestic, encyclopaedic quality that is simultaneously the strength and the weakness of Eilenberg's contributions. The book begins with a fairly terse exposition, in Chapters 1 to 3, of basic semigroup theory up to the Schutzenberger representations and the Rees- Suschkewitz Theorem. This is well done, though an inexperienced postgraduate student might find it difficult. From Chapter 4 onwards the book develops its own characteristic flavour and launches successively into the prime decomposition theorem for finite monoids, languages, codes, automata, syntactic monoids, rational languages, algebraic (or context-free) languages and Burnside problems. In all this the author's sound grasp of very diverse material is evident, and a strong unifying thread runs throughout. In the final chapter a proof based on Foata [3] is given of MacMahon's Master Theorem [6] of 1915, and it is demonstrated with many applications how this is related to free monoids. The whole book is in fact a treasure- house of combinatorial mathematics and should be in every serious library of mathematics or computational science. By attempting to cover so much ground in a relatively short book the author does occasionally slip into obscurity. The reader who attempted to learn for the first time about Turing machines, computability, recursion, Markov algorithms, etc., by reading Chapter 5 might well be perplexed, as might the reader who tried to find out about Lie algebras from Chapter 11. But by exhibiting the fact, long known for groups, that monoids constitute an important unifying principle in mathematics the author has performed a valuable service. One final frivolous remark: on page 302, in investigating the order of a free band on k generators, the author introduces a number c_j defined by c_1 = 1, c_j = j^2 c_{j-1}^2 and then, somewhat rashly, shows the rapid growth of this number for increasing j by calculating its value up to j = 5. His value of 11,075,314,176 for c_5 is not even plausible, since the recursion formula makes it clear that c_5 is divisible by 25. For a value of c_5 which is certainly different, and which may even be correct, see the reviewer's book [5, p. 108]. References 1. A. H. Clifford and G. B. Preston, The algebraic theory of semigroups (volumes 1 and 2, American Math. Soc, 1961 and 1967). 2. S. Eilenberg, Automata, languages and machines (volumes A and B, Academic Press, 1974 and 1976). 3. D. Foata, Etude algebrique de certains problemes d'analyse combinatoire et du calcul des probabilites, Publ. Inst. Stat. Univ. Paris 14 (1965), 81-214. 4. E. Hille and R. S. Phillips, Functional analysis and semigroups (American Mathematical Society, 1957). 5. J. M. Howie, An introduction to semigroup theory (Academic Press, 1976). 6. P. A. MacMahon, Combinatory analysis I (Cambridge University Press, 1915). JOHN M. HOWIE