Automatic Sequences: Theory, Applications, Generalizations

Jean-Paul Allouche and Jeffrey Shallit
Automatic Sequences: Theory, Applications, Generalizations,
Cambridge University Press, 2003.

  The authors talking to each other.

Table of Contents

This is a book about sequences generated by finite automata, and their generalizations, with applications to number theory and theoretical physics. The chapters are as follows:
  1. Stringology. Basic notions about words and combinatorics on words.
  2. Number Theory and Algebra. The mathematical prerequisites for the rest of the book.
  3. Numeration Systems. Representing integers and real numbers as strings of symbols in various ways.
  4. Finite Automata and Other Models of Computation.
  5. Automatic Sequences. We finally get to the main topic of the book.
  6. Uniform Morphisms and Automatic Sequences.
  7. Morphic Sequences. A generalization of automatic sequences, discussing those sequences obtained by iterating morphisms.
  8. Frequency of Letters. Theorems about how often a given letter can occur in automatic and morphic sequences.
  9. Characteristic Words. A special class of sequences with interesting properties.
  10. Subwords. How many subwords of a given length are there, etc.
  11. Cobham's Theorem. When a sequence can be both k- and l-automatic.
  12. Formal Power Series. Christol's theorem and transcendence.
  13. Automatic Real Numbers. Real numbers whose base-k expansion forms an automatic sequence. Applications to transcendence.
  14. Multdimensional Automatic Sequences. Two-dimensional sequences (tables) generated by automata.
  15. Automaticity. Sequences that are "close to" automatic.
  16. k-regular Sequences. Another generalization of automatic sequences.
  17. Physics. Applications of the theory to theoretical physics.
The book has 460 exercises, some with solutions. There are over 1600 citations to the literature.

Fun Things About the Book

  • The cover of the book was designed by James F. Brisson, based on a morphism originally discovered by Jeff Haferman. The cover has a neat optical illusion! If you look at the cover face on, about 2 inches (5 cm) below the name "Allouche", with ambient light illumination (not direct light), the yellow-orange and red parts of the design seem to be on two different levels. (I see the red parts as floating about 2 mm below the rest of the design, but most other people see the red parts floating above.) The illusion is even more dramatic if you continue to focus on the cover, but rotate your head from side to side.

  • There are some jokes in the index. See if you can find them.

    Errata

    Here is a postscript file with the current errata list. Here is a pdf version.

    Comments from Readers

    "The book is very well written, and contains a tremendous amount of information... Advanced students and researchers will delight in reading Automatic Sequences."
    -- Michel Mendès France, Université de Bordeaux, writing in Bull. London Math. Soc. 36 (2004), 573-576.

    "I strongly recommend this excellent book to anybody interested in interaction between theoretical computer science and mathematics."
    -- Jean Berstel, Institut Gaspard Monge, writing in SIGACT News, Vol. 35 No. 1 (March 2004), pp. 12-16

    "Every serious sequence lover will want to own a copy!"
    -- Neil Sloane, AT & T Research

    "...this book will soon become the Bible on the subject..."
    -- Jia-Yan Yao, Wuhan University

    "It is a wealth of information and I am really enjoying reading it."
    -- Luca Q. Zamboni, University of North Texas

    "The book is a successful combination of a monograph (almost encyclopedic) and an introduction to the subject. Professional mathematicians and theoretical computer scientists will find the most important results, applications and examples of the theory, with motivation, cleverly collected and clearly represented. Selected applications in number theory, combinatorics on words and physics show the strength of the theory. Lists of open questions show the way for further development. All this is supplemented with a bibliographical notes and comments, and an impressive list of references... This is a good and carefully written book by two experts in the field."
    -- Guentcho Skordev, University of Bremen

    "Allouche and Shallit's book presents an introduction to the fascinating subject of automatic sequences ...This book, which incorporates results from both mathematics and computer science, will be very valuable to a large audience."
    -- Francine Blanchet-Sadri, writing in Zentralblatt

    See the complete review in Zentralblatt Math.

    "Beautifully presented in a concise and scholarly manner, this book develops the fascinating theory of sequences generated by one of the most basic models of computation; namely, finite automata... Allouche and Shallit ... manage to successfully combine a myriad of concepts from a range of seemingly disparate disciplines to form a coherent and extremely informative resource for anyone from the professional researcher to the inquisitive undergraduate student... Applicable to practically all areas of mathematics and computer science, this book is sure to become a much celebrated text on infinite sequences of symbols and their applications. A worthy addition to every mathematician's bookcase!"
    -- Amy Glen, writing in Gazette of the Australian Mathematical Society, September 2004

    See the complete review.

    Addenda

    As we learn about new results that are relevant, we'll list them here.

    E-mail: