Magic Numbers in Periodic Automatic Sequences

Automatic sequences are a family of sequences described by finite automata with output. The sequence (a_n) is automatic in base b, or b-automatic, if there is an automaton with output A such that A outputs a_n when given the base-b representation of n as an input. Such sequences were introduced by Büchi in 1960 and provide a notion of ease of definability with regards to base b, in the sense that properties related to base-b expansions correspond to b-automatic sequences. Additionally, the level of complexity of a sequence can be measured by the number of states of the smallest automaton that produces it. Periodic sequences are another family of sequences that occupy a low level on the scale of complexity. For instance, they are exactly the sequences that have bounded factor complexity (a result by Morse and Hedlund; on the other hand, automatic sequences have at most linear factor complexity). These are linked to automatic sequences by Cobham's theorem (1972) that characterises sequences simultaneously automatic in multiple bases. In this work, we further investigate the link between periodicity and description by automata, by characterising the sizes of smallest base-l automata that generate periodic sequences of period k. This enables a better understanding of sequences on the lower end of the complexity scale. Joint work with Manon Stipulanti, Luca Prigioniero and Eric Rowland. See Magic Numbers in Periodic Sequences, in: Anna Frid, Robert Mercas (eds), Combiatorics on Words. WORDS 2023. LNCS vol. 13899, Springer, Cham.

Authors

• Savinien Kreczman

Keywords

No keywords are indexed for this paper.