Complexity of automatic sequences

Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties, such as the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences, like removing or adding an initial element, combining sequences, or taking arithmetic subsequences, and observe that these operations may increase the complexity at most polynomially. For periodic sequences we give sharp bounds for both complexity measures.

Authors

• Hans Zantema
• Wieb Bosma

Keywords

No keywords are indexed for this paper.