Automatic sequence

In mathematics and theoretical computer science, an automatic sequence (called a k-automatic 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 the sequence is a mapping of the final state of the automaton when its input is the digits of the number 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]

Definition

Let k \geq 2. The k-kernel of the sequence s(n)_{n \geq 0} is the set of sequences

\{s(k^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}.

A sequence s(n)_{n \geq 0} is k-automatic if its k-kernel is finite.

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

Examples

The following sequences are automatic:

 (1+z)^3 T^2 + (1+z)^2 T + z = 0 \
over the field F2(z).[10]

Automaton point of view

Let k be a positive integer, and D = (E, {0,1,...,k-1}, φ, e, E) be a deterministic finite automaton where

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:

φ(e,s) = φ(φ(e, s1s2...st-1), st).

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

m(n) = π(φ(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

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

Properties

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.[19] This theorem is also due to Cobham,[20] with a multidimensional generalisation due to Semënov.[21][22]

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

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

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).[26]

Decimation

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 and only if the k-decimation kernel is finite.[27][28][29]

Generalizations

k-automatic sequences are generalized to infinite alphabets by k-regular sequences.

1-automatic sequences

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.

Automatic real numbers

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

See also

Notes

  1. 1 2 3 4 Allouche & Shallit (2003) p. 152
  2. 1 2 3 Berstel et al (2009) p. 78
  3. Allouche & Shallit (2003) p. 168
  4. 1 2 3 Pytheas Fogg (2002) p. 13
  5. Pytheas Fogg (2002) p. 15
  6. Lothaire (2005) p. 524
  7. Lothaire (2005) p. 528
  8. 1 2 Lothaire (2005) p. 525
  9. 1 2 Berstel & Reutenauer (2011) p. 92
  10. Berstel & Reutenauer (2011) p. 94
  11. Allouche & Shallit (2003) p. 154
  12. Allouche & Shallit (2003) p. 156
  13. Allouche & Shallit (2003) p. 155
  14. Lothaire (2005) p. 526
  15. Allouche & Shallit (2003) p. 183
  16. Allouche & Shallit (2003) p. 176
  17. Allouche & Shallit (2003) p. 212
  18. Allouche & Shallit (2003) p. 175
  19. Allouche & Shallit (2003) pp. 345–350
  20. Cobham, Alan (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory 3 (2): 186–192. doi:10.1007/BF01746527.
  21. Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian) 18: 403–418.
  22. Point, F.; Bruyère, V. (April 1997). "On the Cobham-Semenov theorem". Theory of Computing Systems 30 (2): 197–220. doi:10.1007/BF02679449.
  23. Lothaire (2005) p. 529
  24. Berstel & Reutenauer (2011) p. 103
  25. Lothaire (2005) p. 532
  26. Berstel & Reutenauer (2011) p. 93
  27. Allouche & Shallit (2003) p. 185
  28. Lothaire (2005) p. 527
  29. Berstel & Reutenauer (2011) p. 91
  30. Shallit (1999) p. 556
  31. 1 2 Allouche & Shallit (2003) p. 379
  32. 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
  33. 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

References

This article is issued from Wikipedia - version of the Tuesday, April 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.