Automatic sequence

In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.^[1]^[2]

An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χ_S is an automatic sequence; that is, S is k-automatic if χ_S(n) is k-automatic, where χ_S(n) = 1 if n $\in$ S and 0 otherwise.^[3]^[4]

Definition

Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows.

Automata-theoretic

Let k be a positive integer, and let D = (Q, Σ_k, δ, q₀, Δ, τ) be a deterministic finite automaton with output, where

Q is the finite set of states;
the input alphabet Σ_k consists of the set {0,1,...,k-1} of possible digits in base-k notation;
δ : Q × Σ_k → Q is the transition function;
q₀ ∈ Q is the initial state;
the output alphabet Δ is similar to Σ_k; and
τ : Σ_k → Δ is the output function mapping from the input alphabet to the output alphabet.

Extend the transition function δ from acting on single digits to acting on strings of digits by defining the action of δ on a string s consisting of digits s₁s₂...s_t as:

δ(q,s) = δ(δ(q₀, s₁s₂...s_t-1), s_t).

Define a function a from the set of positive integers to the output alphabet Δ as follows:

a(n) = τ(δ(q₀,s(n))),

where s(n) is n written in base k. Then the sequence a = a(1)a(2)a(3)... is a k-automatic sequence.^[1]

An automaton reading the base k digits of s(n) starting with the most significant digit is said to be direct reading, while an automaton starting with the least significant digit is reverse reading.^[4] The above definition holds whether s(n) is direct or reverse reading.^[5]

Substitution

Let φ be a k-uniform morphism of a free monoid Σ^∗ and let τ be defined as in the automata-theoretic case. If w is a fixed point of φ—that is, if w = φ(w)—then s = τ(w) is a k-automatic sequence.^[6] This result is due to Cobham, and it is referred to in the literature as Cobham's theorem.^[2]^[7] Conversely, every k-automatic sequence is obtainable in this way.^[4]

k-kernel

Let k ≥ 2. The k-kernel of the sequence s(n) is the set of subsequences

K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.

In most cases, the k-kernel of a sequence is infinite. However, if the k-kernel is finite, then the sequence s(n) is k-automatic.^[8]^[9]^[10]

It follows that a k-automatic sequence is necessarily a sequence on a finite alphabet.

History

Automatic sequences were introduced by Büchi in 1960,^[11] although his paper took a more logico-theoretic approach to the matter and did not use the terminology found in this article. The notion of automatic sequences was further studied by Cobham in 1972, who called these sequences "uniform tag sequences".^[7] The term "automatic sequence" first appeared in a paper of Deshouillers.^[12]

Examples

The following sequences are automatic:

Thue–Morse sequence

The Thue–Morse sequence is the fixed point of the morphism 0 → 01, 1 → 10. Since the n-th term of the Thue–Morse sequence counts the number of ones modulo 2 in the base-2 representation of n, it is generated by the two-state deterministic finite automaton with output pictured here, where being in state q₀ indicates there are an even number of ones in the representation of n and being in state q₁ indicates there are an odd number of ones. Hence, the Thue–Morse sequence is 2-automatic.

Period-doubling sequence

The n-th term of the period-doubling sequence, d(n), is determined by the parity of the exponent of the highest power of 2 dividing n. It is also the fixed point of the morphism 0 → 01, 1 → 00.^[13] Starting with the initial term w = 0 and iterating the 2-uniform morphism φ on w where φ(0) = 01 and φ(1) = 00, it is evident that the period-doubling sequence is the fixed-point of φ(w) and thus it is 2-automatic.

Rudin–Shapiro sequence

The n-th term of the Rudin–Shapiro sequence, r(n), is determined by the number of consecutive ones in the base-2 representation of n. The 2-kernel of the Rudin–Shapiro sequence^[14] is

{\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}

Since the 2-kernel consists only of r(n), r(2n + 1), r(4n + 3), and r(8n + 3), it is finite and thus the Rudin–Shapiro sequence is 2-automatic.

Other sequences

Both the Baum–Sweet sequence^[15] and the regular paperfolding sequence^[16]^[17]^[18] are automatic. In addition, the general paperfolding sequence with a periodic sequence of folds is also automatic.^[19]

Properties

Automatic sequences exhibit a number of interesting properties. A non-exhaustive list of these properties is presented below.

Every automatic sequence is a morphic word.^[20]
For k ≥ 2 and r ≥ 1, a sequence is k-automatic if and only if it is k^r-automatic. This result is due to Eilenberg.^[21]
For h and k multiplicatively independent, a sequence is both h-automatic and k-automatic if and only if it is ultimately periodic.^[22] This result is due to Cobham,^[23] with a multidimensional generalisation due to Semenov.^[24]^[25]
If u(n) is a k-automatic sequence over an alphabet Σ and f is a uniform morphism from Σ^∗ to another alphabet Δ^∗, then f(u) is a k-automatic sequence over Δ.^[26]
If u(n) is a k-automatic sequence, then the sequences u(kⁿ) and u(kⁿ − 1) are ultimately periodic.^[27] Conversely, if u(n) is an ultimately periodic sequence, then the sequence v defined by v(kⁿ) = u(n) and otherwise zero is k-automatic.^[28]
Let u(n) be a sequence over an alphabet Σ and suppose that there is an injective function β from Σ to the finite field F_q, where q = pⁿ for some prime p. The associated formal power series is

\sum _{i\geq 0}\beta (u(i))X^{i}.

Then the sequence u is q-automatic if and only if this formal power series is algebraic over F_q(X). This result is due to Christol, and it is referred to in the literature as Christol's theorem.^[29]

1-automatic sequences

k-automatic sequences are normally only defined for k ≥ 2.^[1] The concept can be extended to k = 1 by defining a 1-automatic sequence to be a sequence whose n-th term depends on the unary notation for n; that is, (1)ⁿ. Since a finite state automaton must eventually return to a previously visited state, all 1-automatic sequences are ultimately periodic.

Generalizations

Automatic sequences are robust against variations to either the definition or the input sequence. For instance, as noted in the automata-theoretic definition, a given sequence remains automatic under both direct and reverse reading of the input sequence. A sequence also remains automatic when the base is changed or when the base is negated; that is, when the input sequence is represented in base −k instead of in base k.^[30]

The domain of an automatic sequence can be extended from the natural numbers to the integers via two-sided automatic sequences. This stems from the fact that, given k ≥ 2, every integer can be represented uniquely in the form $\sum _{0\leq i\leq r}a_{i}(-k)^{i},$ where $a_{i}\in \{0,\dots ,k-1\}$ . Then a two-sided infinite sequence a(n)_{n $\in \mathbb {Z}$} is (−k)-automatic if and only if its subsequences a(n)_{n ≥ 0} and a(−n)_{n ≥ 0} are k-automatic.^[31]

The alphabet of a k-automatic sequence can be extended to infinite alphabets by k-regular sequences.^[32]

Notes

^ ^a ^b ^c Allouche & Shallit (2003) p. 152
^ ^a ^b Berstel et al (2009) p. 78
^ Allouche & Shallit (2003) p. 168
^ ^a ^b ^c Pytheas Fogg (2002) p. 13
^ Pytheas Fogg (2002) p. 15
^ Allouche & Shallit (2003) p. 175
^ ^a ^b Cobham (1972)
^ Allouche & Shallit (2003) p. 185
^ Lothaire (2005) p. 527
^ Berstel & Reutenauer (2011) p. 91
^ Büchi, J. R. (1960). "Weak second-order arithmetic and finite automata". Z. Math. Logik Grundlagen Math. 6: 66–92. doi:10.1007/978-1-4613-8928-6_22.
^ Deshouillers, J.-M. (1979–1980). "La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux: 5.01 – 5.22.
^ Allouche & Shallit (2003) p. 176
^ Allouche & Shallit (2003) p. 186
^ Allouche & Shallit (2003) p. 156
^ Berstel & Reutenauer (2011) p. 92
^ Allouche & Shallit (2003) p. 155
^ Lothaire (2005) p. 526
^ Allouche & Shallit (2003) p. 183
^ Lothaire (2005) p. 524
^ Eilenberg, Samuel (1974). Automata, languages, and machines. Vol. A. Orlando: Academic Press. ISBN 0-122-34001-9.
^ Allouche & Shallit (2003) pp. 345–350
^ Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527.
^ Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian). 18: 403–418.
^ Point, F.; Bruyère, V. (1997). "On the Cobham-Semenov theorem". Theory of Computing Systems. 30 (2): 197–220. doi:10.1007/BF02679449.
^ Lothaire (2005) p. 532
^ Lothaire (2005) p. 529
^ Berstel & Reutenauer (2011) p. 103
^ Christol, G. (1979). "Ensembles presque périodiques k-reconnaissables". Theoret. Comput. Sci. 9: 141–145.
^ Allouche & Shallit (2003) p. 157
^ Allouche & Shallit (2003) p. 162
^ Allouche, J.-P.; Shallit, J. (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98: 163–197, doi:10.1016/0304-3975(92)90001-v

References

Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
Cobham, Alan (1972). "Uniform tag sequences". Math. Systems Theory. 6: 164–192. doi:10.1007/BF01706087.
Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.