Complexity of automatic sequences (Q5896135)

Given an infinite sequence that takes finitely many values, there are several ways of giving a measure of ``how complicated'' the sequence is. Several of these measures count factors (i.e., finite blocks of elements occurring consecutively in the sequence), or factors of a special kind (e.g., palindromic factors). A reasonable requirement is that ``random'' sequences should have a large complexity, while sequences that can be generated by some algorithm should have a small complexity. Further, a ``simpler'' algorithm should give a sequence with smaller complexity. In the paper under review the author studies only \textit{automatic sequences}. These sequences are given by automata with output: the element of index \(n\) of the sequence generated by such an automaton is obtained by feeding the automaton with the digits of \(n\) in some fixed base, after having chosen a fixed way to read the digits, namely either forward or backward. (Recall that the set of ``forward automatic sequences'' is equal to the set of ``backward automatic sequences''.) For each automatic sequence, the author considers the minimal (in size) forward and backward automata that produce the sequence, and calls their sizes the (forward or backward) complexity of the considered automatic sequence. These complexities are compared with the cardinality of the \(q\)-kernel of the sequence and with the size of the minimal alphabet in the morphic definition of the sequence. A first result is that there exist sequences for which one of the complexities is exponentially larger than the other one. Then, the variation of the complexity under some basic operations is studied, e.g., when removing a prefix of the sequence, when gluing elements at the beginning of the sequence, or when taking a subsequence along an arithmetic progression of the indices. The last part of the paper, about the case of periodic sequences, cites in particular a preprint of \textit{W. Bosma} [``Complexity of periodic sequences'', Preprint, \url{https://www.math.ru.nl/~bosma/pubs/periodic.pdf}]. Note that both this preprint and the paper under review are developed in the recent paper by these two authors [\textit{H. Zantema} and \textit{W. Bosma}, ``Complexity of automatic sequences'', Inf. Comput. (to appear; \url{doi:10.1016/j.ic.2021.104710})]. For the entire collection see [Zbl 1435.68034].