Kalpana Kalpana (Editor)

Automatic sequence

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

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. However the two directions lead to the same class of sequences.

Every automatic sequence is a morphic word.

Definition

Let k ≥ 2 . The k-kernel of the sequence s ( n ) n ≥ 0 is the set of sequences

{ s ( k e n + r ) n ≥ 0 : e ≥ 0  and  0 ≤ r ≤ k e − 1 } .

A sequence s ( n ) n ≥ 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:

  • The Thue–Morse sequence 01101001100101101001011001101001... is the fixed point of the morphism 0 → 01, 1 → 10. The 2-kernel consists of the sequence itself and its complement. Hence the Thue–Morse sequence is 2-automatic. The n-th term is the parity of the sum of digits in the base-2 representation of n. The associated power series T(z) satisfies
    • over the field F2(z).
  • Rudin–Shapiro sequence
  • Baum–Sweet sequence
  • Regular paperfolding sequence and a general paperfolding sequence with a periodic sequence of folds
  • The period-doubling sequence, defined by the parity of the power of 2 dividing n; it is the fixed point of the morphism 0 → 01, 1 → 00.

    • 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

  • E is the finite set of states
  • the alphabet consists of the set {0,1,...,k-1} of possible digits in base-k notation
  • φ : E×{0,1,...,k−1} → E is the transition function
  • e ∈ E is the initial state
  • every state is an accept state

    • also let A be a finite set, and π:E → A 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.

    Substitution point of view

    Let σ be a k-uniform morphism of the free monoid E∗, so that σ ( E ) ⊆ E k and which is prolongable on e ∈ 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: this is Cobham's theorem. Conversely every k-automatic sequence is obtained in this way.

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

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

    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.

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

    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.

    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. 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. All such numbers are either rational or transcendental, but not a U-number. Rational numbers are k-automatic in base b for all k and b.

    References

    Automatic sequence Wikipedia
    (Text) CC BY-SA