Automatic sequence
   HOME

TheInfoList



OR:

In mathematics and
theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...
, 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 In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
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''.Allouche & Shallit (2003) p. 152Berstel et al (2009) p. 78 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.


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 An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, and let ''D'' = (''Q'', Σ''k'', δ, ''q0'', Δ, τ) be a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state autom ...
''with output'', where *''Q'' is the finite set of states; *the input alphabet Σ''k'' consists of the set 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 ''s''1''s''2...''s''''t'' as: :δ(''q'',''s'') = δ(δ(''q'', ''s''1''s''2...''s''''t''-1), ''s''''t''). 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''.Pytheas Fogg (2002) p. 13 The above definition holds whether ''s''(''n'') is direct or reverse reading.Pytheas Fogg (2002) p. 15


Substitution

Let \varphi be a ''k''- uniform morphism of a
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
\Sigma^* and let \tau be a ''coding'' (that is, a 1-uniform morphism), as in the automata-theoretic case. If w is a fixed point of \varphi—that is, if w = \varphi(w)—then s = \tau(w) is a ''k''-automatic sequence.Allouche & Shallit (2003) p. 175 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''.Cobham (1972)


''k''-kernel

Let ''k'' ≥ 2. The ''k-kernel'' of the sequence ''s''(''n'') is the set of subsequences :K_(s) = \. 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.Allouche & Shallit (2003) p. 185Lothaire (2005) p. 527Berstel & Reutenauer (2011) p. 91 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 In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
F''q'', where ''q'' = ''p''''n'' for some prime ''p''. The associated formal power series is : \sum_ \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''.


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 In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
''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 ''q''0 indicates there are an even number of ones in the representation of ''n'' and being in state ''q''1 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.Allouche & Shallit (2003) p. 176 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 In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2- automatic sequence named after Marcel Golay, Walter Rudin, and Harold S. Shapiro, who independently investigated its properties. ...
''r''(''n'') () is determined by the number of consecutive ones in the base-2 representation of ''n''. The 2-kernel of the Rudin–Shapiro sequenceAllouche & Shallit (2003) p. 186 is : \begin 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 Since the 2-kernel consists only of ''r''(''n''), ''r''(2''n'' + 1), ''r''(4''n'' + 3), and ''r''(8''n'' + 3), it is finite and thus the Rudin–Shapiro sequence is 2-automatic.


Other sequences

Both the Baum–Sweet sequenceAllouche & Shallit (2003) p. 156 () and the
regular paperfolding sequence In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite sequence of 0s and 1s. It is obtained from the repeating partial sequence by filling in the question marks by another copy of the whole sequen ...
Berstel & Reutenauer (2011) p. 92Allouche & Shallit (2003) p. 155Lothaire (2005) p. 526 () are automatic. In addition, the general paperfolding sequence with a periodic sequence of folds is also automatic.Allouche & Shallit (2003) p. 183


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 In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid. Every automatic sequence is morphic. Definition Let ''f'' ...
.Lothaire (2005) p. 524 *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. *For ''h'' and ''k'' multiplicatively independent, a sequence is both ''h''-automatic and ''k''-automatic if and only if it is ultimately periodic.Allouche & Shallit (2003) pp. 345–350 This result is due to Cobham also known as Cobham's theorem, with a multidimensional generalisation due to Semenov. *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 Δ.Lothaire (2005) p. 532 *If ''u''(''n'') is a ''k''-automatic sequence, then the sequences ''u''(''k''''n'') and ''u''(''k''''n'' − 1) are ultimately periodic.Lothaire (2005) p. 529 Conversely, if ''u''(''n'') is an ultimately periodic sequence, then the sequence ''v'' defined by ''v''(''k''''n'') = ''u''(''n'') and otherwise zero is ''k''-automatic.Berstel & Reutenauer (2011) p. 103


Proving and disproving automaticity

Given a candidate sequence s = (s_n)_, it is usually easier to disprove its automaticity than to prove it. By the ''k''-kernel characterization of ''k''-automatic sequences, it suffices to produce infinitely many distinct elements in the ''k''-kernel K_k(s) to show that s is not ''k''-automatic. 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. For example, let :t = 011010011\dots be the Thue–Morse word. Let s be the word given by concatenating successive terms in the sequence of run-lengths of t. Then s begins :s = 12112221\dots.. It is known that s is the fixed point h^(1) of the morphism :h(1) = 121, h(2) = 12221. The word s is not 2-automatic, but certain elements of its 2-kernel agree for many terms. For example, s_ = s_ \text 0 \le n \le 1864134 but not for n = 1864135. 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. Let (s_n)_ written in the alphabet \Delta, and let (n)_k denote the base-k expansion of n. Then the sequence s = (s_n)_ is k-automatic if and only each of the fibres :I_k(s,d) := \ is a regular language. Checking regularity of the fibres can often be done using the
pumping lemma for regular languages Pumping may refer to: * The operation of a pump, for moving a liquid from one location to another **The use of a breast pump for extraction of milk * Pumping (audio), a creative misuse of dynamic range compression * Pumping (computer systems), the ...
. If s_k(n) denotes the sum of the digits in the base-k expansion of n and p(X) is a polynomial with non-negative integer coefficients, and if k \ge 2, m \ge 1 are integers, then the sequence :(s_k(p(n)) \pmod)_ is k-automatic if and only if \deg p \le 1 or m \mid k-1.


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)''n''. 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 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''.Allouche & Shallit (2003) p. 157 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 \sum_ a_(-k)^ , where a_ \in \. Then a two-sided infinite sequence ''a''(''n'')''n'' \in \mathbb is (−''k'')-automatic if and only if its subsequences ''a''(''n'')n ≥ 0 and ''a''(−''n'')n ≥ 0 are ''k''-automatic.Allouche & Shallit (2003) p. 162 The alphabet of a ''k''-automatic sequence can be extended from finite size to infinite size via ''k''-regular sequences. The ''k''-regular sequences can be characterized as those sequences whose ''k''-kernel is finitely-generated. Every bounded ''k''-regular sequence is automatic.


Logical approach

For many 2-automatic sequences s = (s_n)_, the map n \mapsto s_n has the property that the first-order theory \text(\mathbb,+,0,1,n \mapsto s_n) is decidable. 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. For example, the following properties of the Thue–Morse word can all be verified mechanically in this way: *The Thue–Morse word is overlap-free, i.e., it does not contain a word of the form cxcxc where c is a single letter and w is a possibly empty word. *A non-empty word x is ''bordered'' if there is a non-empty word w and a possibly empty word y with x = wyw. The Thue–Morse word contains a bordered factor for each length greater than 1. *There is an unbordered factor of length n in the Thue–Morse word if and only if (n)_2 \notin 1(01^*0)^*10^*1 where (n)_2 denotes the binary representation of n. The software Walnut, 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.


See also

* Büchi arithmetic


Notes


References

* * * * * *


Further reading

* * * * {{DEFAULTSORT:Automatic Sequence Combinatorics on words Automata (computation) Integer sequences