Automatic Sequences
\textit{Words} (or \textit{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\). Computer Science uses \textit{computational models} to idealize computers. One of the simplest models, called the \textit{deterministic finite automaton}, is a 5--tuple \(M = (Q, \Sigma, \delta, q_0, F)\), where \(Q\) is a finite set called the \textbf{set of states}, \(\Sigma\) is a finite set called the \textbf{input alphabet}, \(\delta: Q \times \Sigma \rightarrow Q\) is the \textbf{transition function}, \(q_0 \in Q\) is the \textbf{initial state}, and \(F \subseteq Q\) is the \textbf{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 \(\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). Another model of computation, called the \textit{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 \textit{output alphabet}, and \(\tau: Q \rightarrow \Delta\) is the \textit{output function}. 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))\). A sequence \(a_0 a_1 \ldots\) over a finite alphabet \(\Delta\) is \textit{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. 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. 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 \textit{uniform tag sequences}, in analogy with Post's process of tag, and also under the name \textit{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: \textit{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. \textit{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\). 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 \(\Sigma_2\), the so-called \textit{characteristic sequences}, which are of great number-theoretic interest and which generalize the Fibonacci sequence. \textit{Sturmian sequences} are also introduced in this chapter. Chapter 10 focuses on the \textit{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. \textit{Generalizations} Several generalizations of automatic sequences are discussed in the book. These include: \textit{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 \textit{D0L sequences}. \textit{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. \textit{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. \textit{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.
- A cyclic binary morphism avoiding abelian fourth powers
- Overlap-freeness in infinite partial words
- On the simplification of infinite morphic words
- Logarithmic frequency in morphic sequences
- Infinite periodic points of endomorphisms over special confluent rewriting systems
- Primitivity of finitely presented monomial algebras.
- Decimations of languages and state complexity
- About frequencies of letters in generalized automatic sequences
- Prime and composite integers close to powers of a number
- The adic realization of the Morse transformation and the extension of its action to the solenoid
- Everywhere -repetitive sequences and Sturmian words
- The class of HDT0L sequences is closed with respect to rational functions
- Avoiding squares and overlaps over the natural numbers
- Pattern spectra, substring enumeration, and automatic sequences
- The ring of k-regular sequences
- The asymptotic distribution of elements in automatic sequences
- Weak repetitions in Sturmian strings.
- The ring of \(k\)-regular sequences. II.
- Arithmetical complexity of symmetric D0L words.
- Möbius disjointness for models of an ergodic system and beyond
- On some arithmetic properties of Mahler functions
- Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
- Substitution-based structures with absolutely continuous spectrum
- Construction of some nonautomatic sequences by cellular automata
- Automatic sequences as good weights for ergodic theorems
- On the pseudorandomness of automatic sequences
- Morphisms on infinite alphabets, countable states automata and regular sequences
- Sequences, groups, and number theory
- Reversing and extended symmetries of shift spaces
- On the regularity of \(\{\lfloor \log_b(\alpha n+\beta)\rfloor\}_{n\geq 0}\)
- On Diophantine exponents for Laurent series over a finite field
- On evil Kronecker sequences and lacunary trigonometric products
- On the k-abelian complexity of the Cantor sequence
- Sturmian images of non Sturmian words and standard morphisms
- Sum of digits and distribution in congruence classes for palindromes with missing digits
- Presentations of topological full groups by generators and relations
- Palindromic subshifts and simple periodic groups of intermediate growth
- Spectra of Schreier graphs of Grigorchuk's group and Schroedinger operators with aperiodic order
- Normality along squares
- On the additive complexity of a Thue-Morse-like sequence
- On a two-valued sequence and related continued fractions in power series fields
- On the \(N\)th linear complexity of automatic sequences
- Well dispersed sequences in \([0,1]^{d}\)
- Factors of generalised polynomials and automatic sequences
- Sturmian numeration systems and decompositions to palindromes
- Ostrowski numeration systems, addition, and finite automata
- Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols
- Distributions of full and non-full words in beta-expansions
- On k-abelian palindromes
- Stochastic dominance for shift-invariant measures
- Automata finiteness criterion in terms of van der Put series of automata functions
- Generalized Thue-Morse sequences of squares
- Algebraic independence results related to pattern sequences in distinct \(\langle q,r \rangle\)-numeration systems
- Self-generating sets, integers with missing blocks, and substitutions
- Mock characters and the Kronecker symbol
- Automatic sequences
- Limit sets of automatic sequences.
- Decidability questions related to abstract numeration systems
- On a universal extraction procedure
- Nonnormality of Stoneham constants
- Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences
- The non-Archimedean theory of discrete systems
- Automatic Dirichlet series
- Effective Erdős-Wintner theorems for digital expansions
- Computing with SN P systems with I/O mode
- Jónsson posets
- Perfect linear complexity profile and apwenian sequences
- Longest arithmetic progressions of palindromes
- Automatic sequences based on Parry or Bertrand numeration systems
- Robustness of Pisot-regular sequences
- Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture
- Nonrepetitive list colorings of the integers
- A characterization of Sturmian sequences by indistinguishable asymptotic pairs
- On \(p\)-adic valuations of certain \(m\) colored \(p\)-ary partition functions
- Minimal automaton for multiplying and translating the Thue-Morse set
- On a family of singular continuous measures related to the doubling map
- On some conjectures of P. Barry
- On the distribution of the truncated sum-of-digits function of polynomial sequences in residue classes
- On decidability of theories of regular languages
- Criteria for apwenian sequences
- A diffraction abstraction
- Substitutive systems and a finitary version of Cobham's theorem
- Regular sequences and synchronized sequences in abstract numeration systems
- Expansions of the group of integers by Beatty sequences
- Multiplicative automatic sequences
- Two arithmetic applications of perturbations of composition operators
- Decidability and \(k\)-regular sequences
- On the 2-abelian complexity of generalized Cantor sequences
- Monochromatic arithmetic progressions in binary Thue-Morse-like words
- Support of an algebraic series as the range of a recursive sequence
- Expansions of generalized Thue-Morse numbers
- Sumsets associated with Beatty sequences
- A refinement of Christol's theorem for algebraic power series
- Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
- How to prove that a sequence is not automatic
- On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values
- Balance and pattern distribution of sequences derived from pseudorandom subsets of \(\mathbb{Z}_q\)
- Automata and finite order elements in the Nottingham group
- Synchronized sequences
- A numeration system for Fibonacci-like Wang shifts
This page was built for publication: Automatic Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4431260)