Automatic sequence

An automatic sequence (or k-automatic sequence) 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 n in some fixed base k. 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.

Automaton point of view

Let q be an integer, and A = (E, φ, e) be a deterministic automaton where

• E is the finite set of states
• φ : E×[0,q − 1] → E is the transition function
• $e\in E$ is the initial state

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

For each n, take m(n) = π(φ(e,$n'$)) where $n'$ is n written in base q. Then the sequence m = m(1)m(2)m(3)... is called a q-automatic sequence.

Substitution point of view

Let σ be a morphism of the free monoid E^* with $\sigma (E)\subseteq E^{q}$, and $e\in E$ such that σ(e) begins by e. Let also be A and π as before. Then if $m'$ is a fixpoint of σ, that is to say $m'$ = σ($m'$), then m = π($m'$) is a q-automatic sequence over A.

1-automatic sequences

k-automatic sequences are normally only defined for k ≥ 2. 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.

Properties

For given k and r, a set is k-automatic if and only if it is k^r-automatic. Otherwise, if h and k are multiplicatively independent, then a set is both h-automatic and k-automatic if and only if it is 1-automatic, that is, ultimately periodic.

Examples

The following sequences are automatic:

• Thue-Morse sequence: take E = A = {0, 1}, e = 0, π = id, and σ such that σ(0) = 01, σ(1) = 10; we get the fixpoint 01101001100101101001011001101001... , which is in fact the Thue-Morse word. The n-th term is the parity of the base 2 representation of n and the sequence is thus 2-automatic.
• Rudin–Shapiro sequence
• Baum–Sweet sequence
• Regular paperfolding sequence

Automatic real number

An automatic real number is a real number for which the base-b expansion is an automatic sequence. All such numbers are either rational or transcendental.

References

• Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003, ISBN 0-521-82332-3
• Dennis A. Hejhal, Emerging applications of number theory, The IMA volumes in mathematics and its applications 109, Springer, 1999, ISBN 0387988246
• J. H. Loxton, "Automata and transcendence", Chapter 13 of New Advances in Transcendence Theory, ed. A. Baker, Cambridge University Press 1988, ISBN 0521335450