Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1086.11015
Allouche, Jean-Paul; Shallit, Jeffrey
Automatic sequences. Theory, applications, generalizations. (English)
[B] Cambridge: Cambridge University Press. xvi, 571~p. \sterling~37.50; \$~50.00/hbk (2003). ISBN 0-521-82332-3/pbk

{\it Words} (or {\it 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 $k \geq 2$, the base-$k$ representation of a non-negative integer $n$ is the unique sequence $(n)_k = a_t a_{t-1} \ldots a_0$ satisfying $n = \sum_{0 \leq i \leq t} a_i k^i$, $a_t \not = 0$, and $a_i \in \Sigma_k = \{0, 1, \ldots, k-1\}$. For $w = b_1 b_2 \ldots b_r$, an inverse operation is defined as $[w]_k = \sum_{1 \leq i \leq r} b_i k^{r-i}$. Clearly, $[(n)_k]_k = n$.\par Computer Science uses {\it computational models} to idealize computers. One of the simplest models, called the {\it deterministic finite automaton}, is a 5--tuple $M = (Q, \Sigma, \delta, q_0, F)$, where $Q$ is a finite set called the {\bf set of states}, $\Sigma$ is a finite set called the {\bf input alphabet}, $\delta: Q \times \Sigma \rightarrow Q$ is the {\bf transition function}, $q_0 \in Q$ is the {\bf initial state}, and $F \subseteq Q$ is the {\bf set of accepting states}.\par Informally, the automaton $M$ is started in state $q_0$ and is fed with an input $w$ (a sequence of symbols or letters from $\Sigma$). Then $M$ moves from state to state according to its transition function $\delta$, while reading the symbols of $w$. When the end of the sequence is reached, $M$ halts in a state $q$ accepting $w$ if $q \in F$ (and rejecting otherwise).\par Another model of computation, called the {\it deterministic finite automaton with output}, is a 6--tuple $M = (Q, \Sigma, \delta, q_0, \Delta, \tau)$, where $Q, \Sigma, \delta, q_0$ are as above, $\Delta$ is a finite set called the {\it output alphabet}, and $\tau: Q \rightarrow \Delta$ is the {\it output function}.\par Such a finite state machine defines a function $f$ from $\Sigma^*$, the set of all sequences over $\Sigma$, to $\Delta$, as $f(w) = \tau(\delta(q_0,w))$ where $\delta(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 $\tau(\delta(q_0,w))$.\par A sequence $a_0 a_1 \ldots$ over a finite alphabet $\Delta$ is {\it k-automatic} if there exists a deterministic finite automaton with output $M = (Q, \Sigma_k, \delta, q_0, \Delta, \tau)$ such that $a_n = \tau(\delta(q_0,w))$ for all $n \geq 0$ 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.\par A theorem of Cobham gives a beautiful description of $k$-automatic sequences in terms of $k$-uniform morphisms. To be more precise, suppose that $\Sigma = \Delta$. A morphism $\varphi: \Delta^* \rightarrow \Delta^*$ is called $k$-uniform if the length of $\varphi(a)$ is $k$ for all $a \in \Delta$. If there exists a letter $a$ such that $\varphi(a) = aw$ for some word $w$ of length $k-1$, then the sequence $aw\varphi(w)\varphi^2 (w) \varphi^3 (w) \ldots$ is the unique infinite fixed point of $\varphi$ 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.\par 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 {\it uniform tag sequences}, in analogy with Post's process of tag, and also under the name {\it 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:\par {\it 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 $\Sigma_k$. Chapter 4 introduces finite automata and other models of computation.\par {\it 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 $k \geq 2$.\par 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$.\par Chapter 9 introduces a class of infinite sequences over $\Sigma_2$, the so-called {\it characteristic sequences}, which are of great number-theoretic interest and which generalize the Fibonacci sequence. {\it Sturmian sequences} are also introduced in this chapter.\par Chapter 10 focuses on the {\it 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 $\ell$-automatic for some multiplicatively independent integers $k$ and $\ell$, then that sequence is ultimately periodic.\par {\it Generalizations} Several generalizations of automatic sequences are discussed in the book. These include:\par {\it 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 {\it D0L sequences}.\par {\it 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.\par {\it 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. {\it 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).\par 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.
[Francine Blanchet-Sadri (Greensboro)]

MSC 2000:: *11B85 Automata sequences
11-01 Textbooks (number theory)
68R15 Combinatorics on words
68Q45 Formal languages

Keywords: Word; sequence; automata; automatic sequence; uniform morphism; morphism; formal languages

Cited in: Zbl 1216.68205 Zbl 1163.11020 Zbl 1143.68038 Zbl 1071.68086

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]