Automatic Sequences: Theory, Applications, Generalizations by Jean-Paul Allouche & Jeffrey Shallit

The book combines concepts and results from mathematics and computer science related to the generation of sequences by simple computational model called the finite automaton.

Even a cursory inspection of the book readily reveals its intended audience. According to the authors, the book might be useful to readers on many levels, from advanced undegraduates to experts in the area. According to the editorial notes, the book is suitable for graduate students and advanced undergraduates, as well as for mature researchers wishing to know more about this fascinating subject. Each chapter, including the introductory ones, contains exercises, notes, and, remarkably, a list of unsolved problems. The bibliography counts over 1600 references, many as recent as 2002.

For a novice or an amateur, the book may prove to be a hard reading, which I think is regretable, since much of the material in the book is of recreational character. First let me mention what is hard about the book.

1. An occasional user will no doubt miss a list of notations. Also, some terms have been omitted from the Index. For example, the notion of integral domain has been neither defined in the book, nor included in the Index, although the terms ring and field were treated with due attention.

2. Most of the time the style is rather terse, if not outright dry. For example, on pages 7-8 the word "define" appears 8 times in 7 consecutive sentences, with 5 of the occurences being "we define".

3. The book has been written for a reader with easy access to a well stocked library. The combined 10 pages of Hints, References, and Solutions to Selected Exercises contain mostly references to a 75-page Bibliography, with say "See Rees [1946]" being quite a representative item in this part of the book.

Of course there are a few misprints, but, far as I can judge, nothing that could hamper an interested reader. Moreover, weighed against the exquisite selection of the material that went into this book, all of the above may look like minor quibbles. The book is just plain rich in small and big ways.

The material in the book is split into 17 chapters, of which the first 4 (Stringology, Number Theory and Algebra, Numeration Systems, Finite Automata and Other Models of Computation) are foundational. Automatic sequences are introduced in Chapter 5.

... to be continued ...

Automatic Sequences: Theory, Applications, Generalizations, by Jean-Paul Allouche & Jeffrey Shallit. Cambridge University Press, 2003. Hardcover, 571 pp, $50.00. ISBN 0-521-82332-3.