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. 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.
An automaton reading the base k digits from the most significant is said to be direct reading, and from the least signficant is reverse reading. However the two directions lead to the same class of sequences.
Every automatic sequence is a morphic word.
Famous quotes containing the words automatic and/or sequence:
“What we learn for the sake of knowing, we hold; what we learn for the sake of accomplishing some ulterior end, we forget as soon as that end has been gained. This, too, is automatic action in the constitution of the mind itself, and it is fortunate and merciful that it is so, for otherwise our minds would be soon only rubbish-rooms.”
—Anna C. Brackett (18361911)
“Reminiscences, even extensive ones, do not always amount to an autobiography.... For autobiography has to do with time, with sequence and what makes up the continuous flow of life. Here, I am talking of a space, of moments and discontinuities. For even if months and years appear here, it is in the form they have in the moment of recollection. This strange formit may be called fleeting or eternalis in neither case the stuff that life is made of.”
—Walter Benjamin (18921940)