Automatic sequences form an important class of infinite sequences: in some sense they describe the simplest pattern to obtain sequences that are not ultimately periodic. We give several equivalent definitions, and provide two natural ways to define the complexity of such sequences, based on sizes of corresponding automata. It turns out that between these two measures there can be an exponential gap. On the other hand, by applying basic operation like adding or removing initial elements, both measures may increase by a polynomial factor at most. This is joined work with Wieb Bosma.
