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. This illusion is called chromostereopsis.

  • 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. For the full review, see here.

    "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.

    "The book can serve both as an introduction into the study of automatic sequences, and as a systematic survey of known results and applications. The topic mentioned in the title is far from being the only interesting theme of the volume. Related topics range from combinatorics on words and formal languages through number theory and formal power series to physics. The basic concept is defined in the fifth chapter using finite automata formalism. In the following chapter an equivalent characterization in terms of fixed points of morphisms is given. Properties of automatic sequences bring together in a natural way results from number theory and theoretical computer science, for example, questions of transcendence of numbers and power series. Relations between these areas are often neglected due to different conventions in language and notation. The book presents a lot of results from both fields for the first time in a unified framework. Material is presented in a clear and attractive way with motivation, exercises, open questions, and a very rich bibliography. The presentation is self-contained in a remarkable degree. The book contains a review of various areas needed such as periodicity in words, subword complexity, algebraic and transcendental numbers, numeration systems, finite automata, Turing machines or continued fractions. Famous sequences like Thue-Morse, Fibonacci or Rudin-Shapiro are also studied. The book will be of use for beginners as well as for advanced students and researchers." -- review by Vladimír Souček in the European Mathematical Society Newsletter, Volume 52, June 2004.

    I highly recommend Automatic Sequences, whether as text, reference, or all the more as an excellent read, both to rank beginners and to those already acquainted with parts of the subject. -- Alf van der Poorten, Mathematics of Computation, 74 (2004), 1039-1040.

    Addenda and Open Problems

    As we learn about new results that are relevant, and solutions to problems we gave as "open", we'll list them here.

    E-mail: