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.
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 S and 0 otherwise.
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, δ, q0, Δ, τ) 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; q0 ∈ Q is the initial state; the output alphabet Δ is a finite set; and τ : Q → Δ is the output function mapping from the set of internal states 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 s1s2...st as:
δ(q,s) = δ(δ(q, s1s2...st-1), st).
Define a function a from the set of positive integers to the output alphabet Δ as follows:
a(n) = τ(δ(q0,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.
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. The above definition holds whether s(n) is direct or reverse reading.
Substitution
Let be a k-uniform morphism of a free monoid and let be a coding (that is, a -uniform morphism), as in the automata-theoretic case. If is a fixed point of —that is, if —then is a k-automatic sequence. Conversely, every k-automatic sequence is obtainable in this way. This result is due to Cobham, and it is referred to in the literature as Cobham's little theorem.
k-kernel
Let k ≥ 2. The k-kernel of the sequence s(n) is the set of subsequences
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, and the converse is also true. This is due to Eilenberg.
It follows that a k-automatic sequence is necessarily a sequence on a finite alphabet.
Formal power series
Let u(n) be a sequence over an alphabet Σ and suppose that there is an injective function β from Σ to the finite field Fq, where q = pn for some prime p. The associated formal power series is
Then the sequence u is q-automatic if and only if this formal power series is algebraic over Fq(X). This result is due to Christol, and it is referred to in the literature as Christol's theorem.
History
Automatic sequences were introduced by Büchi in 1960, 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".
The term "automatic sequence" first appeared in a paper of Deshouillers.
Examples
The following sequences are automatic:
Thue–Morse sequence
The Thue–Morse sequence t(n) () 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 q0 indicates there are an even number of ones in the representation of n and being in state q1 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. 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.