دانلود کتاب 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