zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Automatic sequences. Theory, applications, generalizations. (English) Zbl 1086.11015
Cambridge: Cambridge University Press (ISBN 0-521-82332-3/pbk). xvi, 571 p. £ 37.50; $ 50.00/hbk (2003).

Words (or sequences) are natural objects in several areas of Mathematics and Computer Science. Numbers, for instance, can be represented by sequences over a finite alphabet. For an integer k2, the base-k representation of a non-negative integer n is the unique sequence (n) k =a t a t-1 ...a 0 satisfying n= 0it a i k i , a t 0, and a i Σ k ={0,1,...,k-1}. For w=b 1 b 2 ...b r , an inverse operation is defined as [w] k = 1ir b i k r-i . Clearly, [(n) k ] k =n.

Computer Science uses computational models to idealize computers. One of the simplest models, called the deterministic finite automaton, is a 5–tuple M=(Q,Σ,δ,q 0 ,F), where Q is a finite set called the set of states, Σ is a finite set called the input alphabet, δ:Q×ΣQ is the transition function, q 0 Q is the initial state, and FQ is the set of accepting states.

Informally, the automaton M is started in state q 0 and is fed with an input w (a sequence of symbols or letters from Σ). Then M moves from state to state according to its transition function δ, while reading the symbols of w. When the end of the sequence is reached, M halts in a state q accepting w if qF (and rejecting otherwise).

Another model of computation, called the deterministic finite automaton with output, is a 6–tuple M=(Q,Σ,δ,q 0 ,Δ,τ), where Q,Σ,δ,q 0 are as above, Δ is a finite set called the output alphabet, and τ:QΔ is the output function.

Such a finite state machine defines a function f from Σ * , the set of all sequences over Σ, to Δ, as f(w)=τ(δ(q 0 ,w)) where δ(q 0 ,w) is the state M ends up in when started in state q 0 and fed with the input w. At this point, M outputs the symbol τ(δ(q 0 ,w)).

A sequence a 0 a 1 ... over a finite alphabet Δ is k-automatic if there exists a deterministic finite automaton with output M=(Q,Σ k ,δ,q 0 ,Δ,τ) such that a n =τ(δ(q 0 ,w)) for all n0 and all w satisfying [w] k =n. Several sequences of mathematical interest turn out to be k-automatic for some k: the 2-automatic Thue-Morse sequence, the 2-automatic Rudin-Shapiro sequence, to name a few.

A theorem of Cobham gives a beautiful description of k-automatic sequences in terms of k-uniform morphisms. To be more precise, suppose that Σ=Δ. A morphism φ:Δ * Δ * is called k-uniform if the length of φ(a) is k for all aΔ. If there exists a letter a such that φ(a)=aw for some word w of length k-1, then the sequence awφ(w)φ 2 (w)φ 3 (w)... is the unique infinite fixed point of φ starting with a. Cobham’s result states that a sequence is k-automatic if and only if it is the image (under a coding) of a fixed point of a k-uniform morphism. Thus, automatic sequences are not only generated by finite automata, but are also generated by iterating uniform morphisms.

Allouche and Shallit’s book presents an introduction to the fascinating subject of automatic sequences. This is the first book that systematically develops the theory of these sequences. It brings together results in automata theory and number theory in a consistent and unified framework. In the literature, automatic sequences have been studied under the name uniform tag sequences, in analogy with Post’s process of tag, and also under the name recognizable sequences. The book does assume some mathematical maturity from the reader. The major contents of the book can be divided into several categories which are summarized as follows:

Background material Chapters 1–4 include background material used in the rest of the book. Chapter 1 discusses the basic concepts of finite and infinite words. Chapter 2 reviews knowledge from number theory and algebra. Chapter 3 emphasizes the base-k representation of integers by sequences over the alphabet Σ k . Chapter 4 introduces finite automata and other models of computation.

Theory Chapter 5 defines the fundamental objects of the book: k-automatic sequences, while later chapters explore properties of these sequences. Ultimately periodic sequences turn out to be k-automatic for all k2.

Chapter 6 begins the study of sequences that are fixed points of morphisms focusing on the case of uniform morphisms. Chapter 7 studies the more general case where the morphisms need not be uniform. The famous Fibonacci sequence is the infinite fixed point of the morphism that maps 0 to 01 and 1 to 0. Chapter 8 shows how to prove that some sequences are not k-automatic for any k.

Chapter 9 introduces a class of infinite sequences over Σ 2 , the so-called characteristic sequences, which are of great number-theoretic interest and which generalize the Fibonacci sequence. Sturmian sequences are also introduced in this chapter.

Chapter 10 focuses on the subword complexity of infinite words. An infinite word w may be partially understood by studying its finite subwords. A natural question that arises is: “How many distinct subwords of w of length n are there, and what is the growth rate of this number as n approaches infinity?” This question refers to a measure of complexity, called subword complexity. This measure is of particular interest since automatic sequences have relatively low subword complexity, while random sequences have high such complexity.

Chapter 11 proves a deep theorem due to Cobham which states that if a sequence is both k-automatic and -automatic for some multiplicatively independent integers k and , then that sequence is ultimately periodic.

Generalizations Several generalizations of automatic sequences are discussed in the book. These include:

Morphic sequences Chapter 7 generalizes k-automatic sequences, which are generated by iterating uniform morphisms, to morphic sequences, generated by arbitrary morphisms. Such sequences have been studied in the literature under several names including D0L sequences.

Multidimensional automatic sequences Chapter 14 generalizes k-automatic sequences, which are one-dimensional sequences, to higher-dimensional automatic sequences. This chapter concentrates on the two-dimensional case.

k-regular sequences Chapter 16 generalizes k-automatic sequences, which are defined over finite alphabets, to k-regular sequences, defined over infinite alphabets. There, we can find some examples of k-regular sequences such as the sequence which counts the sum of digits in the base-k representation of a non-negative integer n. The theory of k-regular sequences is closely related to the one of rational series.

Applications Applications of automatic sequences are discussed throughout the book. To cite some examples, applications are found in: Number theory (particularly formal power series and transcendence in finite characteristic (Chapters 9, 12 and 13)); Physics (particularly quasicrystals (Chapter 17)); Computer graphics (Chapter 14); and Music (Chapters 1, 7 and 16).

Allouche and Shallit’s book, mostly self-contained, is suitable for courses in automata theory and number theory at the graduate or advanced undergraduate level. Experts who want to learn more about automatic sequences and their generalizations will also find it useful. Exercises are provided at the end of each chapter, some of which offer the kind of drill undergraduate students need in order to test their understanding, while others are much more substantial problems. Hints, references, and solutions for selected exercises are given in the appendix. Chapters are supplemented by open problems, as well as citations to the literature.

This book, which incorporates results from both Mathematics and Computer Science, will be very valuable to a large audience.


MSC:
11B85Automata sequences
11-01Textbooks (number theory)
68R15Combinatorics on words
68Q45Formal languages and automata