Automatic sequence

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

[3][4] Automatic sequences may be defined in a number of ways, all of which are equivalent.

Let k be a positive integer, and let D = (Q, Σk, δ, q0, Δ, τ) be a deterministic finite automaton with output, where 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: Define a function a from the set of positive integers to the output alphabet Δ as follows: 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.

be a k-uniform morphism of a free monoid

[6] Conversely, every k-automatic sequence is obtainable in this way.

However, if the k-kernel is finite, then the sequence s(n) is k-automatic, and the converse is also true.

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).

[11] Automatic sequences were introduced by Büchi in 1960,[12] although his paper took a more logico-theoretic approach to the matter and did not use the terminology found in this article.

[7] The term "automatic sequence" first appeared in a paper of Deshouillers.

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.

The n-th term of the period-doubling sequence d(n) (OEIS: A096268) 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.

[20] Automatic sequences exhibit a number of interesting properties.

By the k-kernel characterization of k-automatic sequences, it suffices to produce infinitely many distinct elements in the k-kernel

Heuristically, one might try to prove automaticity by checking the agreement of terms in the k-kernel, but this can occasionally lead to wrong guesses.

be the word given by concatenating successive terms in the sequence of run-lengths of

[30] Given a sequence that is conjectured to be automatic, there are a few useful approaches to proving it actually is.

One approach is to directly construct a deterministic automaton with output that gives the sequence.

denotes the sum of the digits in the base-

is a polynomial with non-negative integer coefficients, and if

[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)n. Since a finite state automaton must eventually return to a previously visited state, all 1-automatic sequences are ultimately periodic.

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 an alternate set of digits is used or when the base is negated; that is, when the input sequence is represented in base −k instead of in base k.[33] However, in contrast to using an alternate set of digits, a change of base may affect the automaticity of a sequence.

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

[34] The alphabet of a k-automatic sequence can be extended from finite size to infinite size via k-regular sequences.

Since many non-trivial properties of automatic sequences can be written in first-order logic, it is possible to prove these properties mechanically by executing the decision procedure.

[37] For example, the following properties of the Thue–Morse word can all be verified mechanically in this way: The software Walnut,[40][41] developed by Hamoon Mousavi, implements a decision procedure for deciding many properties of certain automatic words, such as the Thue–Morse word.

This implementation is a consequence of the above work on the logical approach to automatic sequences.