Automatic sequence

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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.[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  S and 0 otherwise.[3][4]

Definition[edit]

Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows.

Automata-theoretic[edit]

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 × ΣkQ is the transition function;
  • q0Q 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) = δ(δ(q0, 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.[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.[5]

Substitution[edit]

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.[6] Conversely, every k-automatic sequence is obtainable in this way.[4] This result is due to Cobham, and it is referred to in the literature as Cobham's little theorem.[2][7]

k-kernel[edit]

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.[8][9][10]

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

Formal power series[edit]

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.[11]

History[edit]

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. The notion of automatic sequences was further studied by Cobham in 1972, who called these sequences "uniform tag sequences".[7]

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

Examples[edit]

The following sequences are automatic:

Thue–Morse sequence[edit]

DFAO generating the Thue–Morse sequence

The Thue–Morse sequence t(n) (OEISA010060) 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[edit]

The n-th term of the period-doubling sequence d(n) (OEISA096268) 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.[14] 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[edit]

The n-th term of the Rudin–Shapiro sequence r(n) (OEISA020985) is determined by the number of consecutive ones in the base-2 representation of n. The 2-kernel of the Rudin–Shapiro sequence[15] is

Since the 2-kernel consists only of r(n), r(2n + 1), r(4n + 3), and r(8n + 3), it is finite and thus the Rudin–Shapiro sequence is 2-automatic.

Other sequences[edit]

Both the Baum–Sweet sequence[16] (OEISA086747) and the regular paperfolding sequence[17][18][19] (OEISA014577) are automatic. In addition, the general paperfolding sequence with a periodic sequence of folds is also automatic.[20]

Properties[edit]

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.[21]
  • For k ≥ 2 and r ≥ 1, a sequence is k-automatic if and only if it is kr-automatic. This result is due to Eilenberg.[22]
  • For h and k multiplicatively independent, a sequence is both h-automatic and k-automatic if and only if it is ultimately periodic.[23] This result is due to Cobham,[24] with a multidimensional generalisation due to Semenov.[25][26]
  • 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 Δ.[27]
  • If u(n) is a k-automatic sequence, then the sequences u(kn) and u(kn − 1) are ultimately periodic.[28] Conversely, if u(n) is an ultimately periodic sequence, then the sequence v defined by v(kn) = u(n) and otherwise zero is k-automatic.[29]

Proving and disproving automaticity[edit]

Given a candidate sequence , 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 to show that 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

be the Thue–Morse word. Let be the word given by concatenating successive terms in the sequence of run-lengths of . Then begins

.

It is known that is the fixed point of the morphism

The word is not 2-automatic, but certain elements of its 2-kernel agree for many terms. For example,

but not for .[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. Let written in the alphabet , and let denote the base- expansion of . Then the sequence is -automatic if and only each of the fibres

is a regular language.[31] Checking regularity of the fibres can often be done using the pumping lemma for regular languages.

If denotes the sum of the digits in the base- expansion of and is a polynomial with non-negative integer coefficients, and if , are integers, then the sequence

is -automatic if and only if or .[32]

1-automatic sequences[edit]

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

Generalizations[edit]

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.[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 where . Then a two-sided infinite sequence a(n)n  is (−k)-automatic if and only if its subsequences a(n)n ≥ 0 and a(−n)n ≥ 0 are k-automatic.[34]

The alphabet of a k-automatic sequence can be extended from finite size to infinite size via k-regular sequences.[35] The k-regular sequences can be characterized as those sequences whose k-kernel is finitely-generated. Every bounded k-regular sequence is automatic.[36]

Logical approach[edit]

For many 2-automatic sequences , the map has the property that the first-order theory 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.[37]

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 where is a single letter and is a possibly empty word.
  • A non-empty word is bordered if there is a non-empty word and a possibly empty word with . The Thue–Morse word contains a bordered factor for each length greater than 1.[38]
  • There is an unbordered factor of length in the Thue–Morse word if and only if where denotes the binary representation of .[39]

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.

See also[edit]

Notes[edit]

  1. ^ a b c Allouche & Shallit (2003) p. 152
  2. ^ a b Berstel et al (2009) p. 78
  3. ^ Allouche & Shallit (2003) p. 168
  4. ^ a b c Pytheas Fogg (2002) p. 13
  5. ^ Pytheas Fogg (2002) p. 15
  6. ^ Allouche & Shallit (2003) p. 175
  7. ^ a b Cobham (1972)
  8. ^ Allouche & Shallit (2003) p. 185
  9. ^ Lothaire (2005) p. 527
  10. ^ Berstel & Reutenauer (2011) p. 91
  11. ^ Christol, G. (1979). "Ensembles presque périodiques k-reconnaissables". Theoret. Comput. Sci. 9: 141–145. doi:10.1016/0304-3975(79)90011-2.
  12. ^ Büchi, J. R. (1960). Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6. pp. 66–92. doi:10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9.
  13. ^ Deshouillers, J.-M. (1979–1980). "La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux: 5.01–5.22.
  14. ^ Allouche & Shallit (2003) p. 176
  15. ^ Allouche & Shallit (2003) p. 186
  16. ^ Allouche & Shallit (2003) p. 156
  17. ^ Berstel & Reutenauer (2011) p. 92
  18. ^ Allouche & Shallit (2003) p. 155
  19. ^ Lothaire (2005) p. 526
  20. ^ Allouche & Shallit (2003) p. 183
  21. ^ Lothaire (2005) p. 524
  22. ^ Eilenberg, Samuel (1974). Automata, languages, and machines. A. Orlando: Academic Press. ISBN 978-0-122-34001-7.
  23. ^ Allouche & Shallit (2003) pp. 345–350
  24. ^ Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527.
  25. ^ Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian). 18: 403–418.
  26. ^ Point, F.; Bruyère, V. (1997). "On the Cobham-Semenov theorem". Theory of Computing Systems. 30 (2): 197–220. doi:10.1007/BF02679449.
  27. ^ Lothaire (2005) p. 532
  28. ^ Lothaire (2005) p. 529
  29. ^ Berstel & Reutenauer (2011) p. 103
  30. ^ Allouche, G.; Allouche, J.-P.; Shallit, J. (2006). "Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde". Annales de l'Institut Fourier. 56 (7): 2126. doi:10.5802/aif.2235.
  31. ^ Allouche and Shallit (2003) p. 160
  32. ^ Allouche and Shallit (2003) p. 197
  33. ^ Allouche & Shallit (2003) p. 157
  34. ^ Allouche & Shallit (2003) p. 162
  35. ^ Allouche, J.-P.; Shallit, J. (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98 (2): 163–197, doi:10.1016/0304-3975(92)90001-v
  36. ^ Shallit, Jeffrey. "The Logical Approach to Automatic Sequences, Part 1: Automatic Sequences and k-Regular Sequences" (PDF). Retrieved April 1, 2020.
  37. ^ Shallit, J. "The Logical Approach to Automatic Sequences: Part 1" (PDF). Retrieved April 1, 2020.
  38. ^ Shallit, J. "The Logical Approach to Automatic Sequences: Part 3" (PDF). Retrieved April 1, 2020.
  39. ^ Shallit, J. "The Logical Approach to Automatic Sequences: Part 3" (PDF). Retrieved April 1, 2020.
  40. ^ Shallit, J. "Walnut Software". Retrieved April 1, 2020.
  41. ^ Mousavi, H. (2016). "Automatic Theorem Proving in Walnut". arXiv:1603.06017 [cs.FL].

References[edit]

Further reading[edit]