k-automatic sequences

[Jeffrey Shallit]

Several people wrote to me asking about k-automatic sequences.

There are many equivalent definitions, but for people interested in
sequences the following definition is probably easiest:  a sequence
(a(n)) is k-automatic if the set of distinct subsequences of the
form (a(k^i n + c))_{n >= 0}, where i >= 0 and 0 <= c < k^i, is finite.

An example is the Thue-Morse sequence, which is defined by t(n) = 1 if
there are an odd number of 1's in the base-2 expansion of n, 0 otherwise.

It is easy to write a program which attempts to deduce if a sequence is
of this form, based on some large number of computed values.  Sometimes
this leads to interesting conjectures.

Another larger class is the k-regular sequences, where we replace 
"finite" by "generates a finitely-generated Z-module".  

Allouche and I are almost done writing a book on k-automatic and k-regular
sequences.

Jeffrey Shallit