Automatic sequence

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

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.[1][2] 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.[3][4]

An automaton reading the base k digits from the most significant is said to be direct reading, and from the least significant is reverse reading.[4] However the two directions lead to the same class of sequences.[5]

Every automatic sequence is a morphic word.[6]

Automaton point of view[edit]

Let k be a positive integer, and D = (E, φ, e) be a deterministic automaton where

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

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

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:

\phi(e, s) = \phi(\phi(e, s_1s_2...s_{t-1}), s_t)\, .

Define a function m from the set of positive integers to the set A as follows:

m(n) = \pi(\phi(e,s(n)))\, ,

where s(n) is n written in base k. Then the sequence m = m(1)m(2)m(3)... is called a k-automatic sequence.[1]

Substitution point of view[edit]

Let σ be a k-uniform morphism of the free monoid E, so that \sigma(E)\subseteq E^k and which is prolongable[7] on e\in E: that is, σ(e) begins with e. Let A and π be defined as above. Then if w is a fixpoint of σ, that is to say w = σ(w), then m = π(w) is a k-automatic sequence over A:[8] this is Cobham's theorem.[2] Conversely every k-automatic sequence is obtained in this way.[4]

Decimation[edit]

Fix k > 1. For a sequence w we define the k-decimations of w for r=0,1,...,k-1 to be the subsequences consisting of the letters in positions congruent to r modulo k. The decimation kernel of w consists of the set of words obtained by all possible repeated decimations of w. A sequence is k-automatic if an only if the k-decimation kernel is finite.[9][10][11]

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 eventually periodic.

Properties[edit]

For given k and r, a set is k-automatic if and only if it is kr-automatic. Otherwise, for h and k multiplicatively independent, then a set is both h-automatic and k-automatic if and only if it is 1-automatic, that is, ultimately periodic.[12]

If u(n) is a k-automatic sequence then the sequences u(kn) and u(kn−1) are ultimately periodic.[13] Conversely, if v(n) is ultimately periodic then the sequence u defined by u(kn) = v(n) and otherwise zero is k-automatic.[14]

Let u(n) be a k-automatic sequence over the alphabet A. If f is a uniform morphism from A to B then the word f(u) is k-automatic sequence over the alphabet B.[15]

Let u(n) be a sequence over the alphabet A and suppose that there is an injective function j from A to the finite field Fq. The associated formal power series is

 f_u(z) = \sum_n j(u(n)) z^n \ .

The sequence u is q-automatic if and only if the power series fu is algebraic over the rational function field Fq(z).[16]

Examples[edit]

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.[1][2][17][18] The 2-kernel consists of the sequence itself and its complement.[19] The associated power series T(z) satisfies
 (1+z)^3 T^2 + (1+z)^2 T + z = 0 \
over the field F2(z).[20]

Automatic real number[edit]

An automatic real number is a real number for which the base-b expansion is an automatic sequence.[27][28] All such numbers are either rational or transcendental, but not a U-number.[29][30] Rational numbers are k-automatic in base b for all k and b.[28]

References[edit]

  1. ^ a b c d Allouche & Shallit (2003) p.152
  2. ^ a b c 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. ^ Lothaire (2005) p.524
  7. ^ Allouche & Shallit (2003) p.212
  8. ^ Allouche & Shallit (2003) p.175
  9. ^ Allouche & Shallitt (2003) p.185
  10. ^ Lothaire (2005) p.527
  11. ^ Berstel & Reutenauer (2011) p.91
  12. ^ Allouche & Shallit (2003) pp.345-350
  13. ^ Lothaire (2005) p.529
  14. ^ Berstel & Reutenauer (2011) p.103
  15. ^ Lothaire (2005) p.532
  16. ^ Berstel & Reutenauer (2011) p.93
  17. ^ a b Lothaire (2005) p.525
  18. ^ a b Berstel & Reutenauer (2011) p.92
  19. ^ Lothaire (2005) p.528
  20. ^ Berstel & Reutenauer (2011) p.94
  21. ^ Allouche & Shallit (2003) p.154
  22. ^ Allouche & Shallit (2003) p.156
  23. ^ Allouche & Shallit (2003) p.155
  24. ^ Lothaire (2005) p.526
  25. ^ Allouche & Shallit (2003) p.183
  26. ^ Allouche & Shallit (2003) p.176
  27. ^ Shallitt (1999) p.556
  28. ^ a b Allouche & Shallit (2003) p.379
  29. ^ Adamczewski, Boris; Bugeaud, Yann (2007), "On the complexity of algebraic numbers. I. Expansions in integer bases", Annals of Mathematics 165 (2): 547–565, doi:10.4007/annals.2007.165.547, Zbl 1195.11094 
  30. ^ Bugeaud, Yann (2012), Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics 193, Cambridge: Cambridge University Press, pp. 192–193, ISBN 978-0-521-11169-0, Zbl pre06066616