Automatic sequence

In mathematics and theoretical computer science, an automatic sequence (called a k-automatic 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 the sequence is a mapping of the final state of the automaton when its input is the digits of the number n in some fixed base k.^[1][2] A k-automatic set is a set of non-negative integers for which the sequence of values of its characteristic function is an automatic sequence: that is, membership of n in the set can be determined by a finite state automaton on the digits of n in base k.^[3][4]

An automaton reading the base k digits from the most significant is said to be direct reading, and from the least significant is reverse reading.^[4] However the two directions lead to the same class of sequences.^[5]

Every automatic sequence is a morphic word.^[6]

Definition

Let $k \geq 2$. The k-kernel of the sequence $s(n)_{n \geq 0}$ is the set of sequences

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

A sequence $s(n)_{n \geq 0}$ is k-automatic if its k-kernel is finite.

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

Examples

The following sequences are automatic:

• The Thue–Morse sequence 01101001100101101001011001101001... is the fixed point of the morphism 0 → 01, 1 → 10. The 2-kernel consists of the sequence itself and its complement.^[7] Hence the Thue–Morse sequence is 2-automatic. The n-th term is the parity of the sum of digits in the base-2 representation of n.^[1][2][8][9] The associated power series T(z) satisfies

$(1+z)^3 T^2 + (1+z)^2 T + z = 0 \$

over the field F₂(z).^[10]

• Rudin–Shapiro sequence^[8][11]
• Baum–Sweet sequence^[12]
• Regular paperfolding sequence^[9][13][14] and a general paperfolding sequence with a periodic sequence of folds^[15]
• The period-doubling sequence, defined by the parity of the power of 2 dividing n; it is the fixed point of the morphism 0 → 01, 1 → 00.^[16]

Automaton point of view

Let k be a positive integer, and D = (E, {0,1,...,k-1}, φ, e, E) be a deterministic finite automaton where

• E is the finite set of states
• the alphabet consists of the set {0,1,...,k-1} of possible digits in base-k notation
• φ : E×{0,1,...,k−1} → E is the transition function
• e ∈ E is the initial state
• every state is an accept state

also let A be a finite set, and π:E → A a projection towards A.

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:

φ(e,s) = φ(φ(e, s₁s₂...s_t-1), s_t).

Define a function m from the set of positive integers to the set A as follows:

m(n) = π(φ(e,s(n))),

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

Substitution point of view

Let σ be a k-uniform morphism of the free monoid E^∗, so that $\sigma(E)\subseteq E^k$ and which is prolongable^[17] on $e\in E$: that is, σ(e) begins with e. Let A and π be defined as above. Then if w is a fixed point of σ, that is to say w = σ(w), then m = π(w) is a k-automatic sequence over A:^[18] this is Cobham's theorem.^[2] Conversely every k-automatic sequence is obtained in this way.^[4]

Properties

For given k and r, a set is k-automatic if and only if it is k^r-automatic. Otherwise, for h and k multiplicatively independent, then a set is both h-automatic and k-automatic if and only if it is 1-automatic, that is, ultimately periodic.^[19] This theorem is also due to Cobham,^[20] with a multidimensional generalisation due to Semënov.^[21][22]

If u(n) is a k-automatic sequence then the sequences u(kⁿ) and u(kⁿ − 1) are ultimately periodic.^[23] Conversely, if v(n) is ultimately periodic then the sequence u defined by u(kⁿ) = v(n) and otherwise zero is k-automatic.^[24]

Let u(n) be a k-automatic sequence over the alphabet A. If f is a uniform morphism from A^∗ to B^∗ then the word f(u) is k-automatic sequence over the alphabet B.^[25]

Let u(n) be a sequence over the alphabet A and suppose that there is an injective function j from A to the finite field F_q. The associated formal power series is

$f_u(z) = \sum_n j(u(n)) z^n \ .$

The sequence u is q-automatic if and only if the power series f_u is algebraic over the rational function field F_q(z).^[26]

Decimation

Fix k > 1. For a sequence w we define the k-decimations of w for r = 0,1,...,k − 1 to be the subsequences consisting of the letters in positions congruent to r modulo k. The decimation kernel of w consists of the set of words obtained by all possible repeated decimations of w. A sequence is k-automatic if and only if the k-decimation kernel is finite.^[27][28][29]

Generalizations

k-automatic sequences are generalized to infinite alphabets by k-regular sequences.

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 eventually periodic.

Automatic real numbers

An automatic real number is a real number for which the base-b expansion is an automatic sequence.^[30][31] All such numbers are either rational or transcendental, but not a U-number.^[32][33] Rational numbers are k-automatic in base b for all k and b.^[31]

See also

• Büchi arithmetic

Notes

1. Allouche & Shallit (2003) p. 152
2. Berstel et al (2009) p. 78
3. Allouche & Shallit (2003) p. 168
4. Pytheas Fogg (2002) p. 13
5. Pytheas Fogg (2002) p. 15
6. Lothaire (2005) p. 524
7. Lothaire (2005) p. 528
8. Lothaire (2005) p. 525
9. Berstel & Reutenauer (2011) p. 92
10. Berstel & Reutenauer (2011) p. 94
11. Allouche & Shallit (2003) p. 154
12. Allouche & Shallit (2003) p. 156
13. Allouche & Shallit (2003) p. 155
14. Lothaire (2005) p. 526
15. Allouche & Shallit (2003) p. 183
16. Allouche & Shallit (2003) p. 176
17. Allouche & Shallit (2003) p. 212
18. Allouche & Shallit (2003) p. 175
19. Allouche & Shallit (2003) pp. 345–350
20. Cobham, Alan (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory 3 (2): 186–192. doi:10.1007/BF01746527.
21. Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian) 18: 403–418.
22. Point, F.; Bruyère, V. (April 1997). "On the Cobham-Semenov theorem". Theory of Computing Systems 30 (2): 197–220. doi:10.1007/BF02679449.
23. Lothaire (2005) p. 529
24. Berstel & Reutenauer (2011) p. 103
25. Lothaire (2005) p. 532
26. Berstel & Reutenauer (2011) p. 93
27. Allouche & Shallit (2003) p. 185
28. Lothaire (2005) p. 527
29. Berstel & Reutenauer (2011) p. 91
30. Shallit (1999) p. 556
31. Allouche & Shallit (2003) p. 379
32. Adamczewski, Boris; Bugeaud, Yann (2007), "On the complexity of algebraic numbers. I. Expansions in integer bases", Annals of Mathematics 165 (2): 547–565, doi:10.4007/annals.2007.165.547, Zbl 1195.11094
33. Bugeaud, Yann (2012), Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics 193, Cambridge: Cambridge University Press, pp. 192–193, ISBN 978-0-521-11169-0, Zbl pre06066616

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 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 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications 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.
• Loxton, J. H. (1988). "13. Automata and transcendence". In Baker, A. New Advances in Transcendence Theory. Cambridge University Press. pp. 215–228. ISBN 0-521-33545-0. Zbl 0656.10032.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
• Rowland, Eric (2015), "What is ... an automatic sequence?", Notices of the American Mathematical Society 62: 274–276.
• Shallit, Jeffrey (1999). "Number theory and formal languages". In Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996. The IMA volumes in mathematics and its applications 109. Springer-Verlag. pp. 547–570. ISBN 0-387-98824-6.