Some improvements of the \(S\)-adic conjecture (Q651048)

A sequence \(w\) over a finite alphabet is called \(S\)-adic if there exist a letter \(a\), a finite set of morphisms \(S\), and a sequence \((\sigma_n)_{n\in\mathbb{N}}\) of morphisms in \(S\) such that \(w=\lim_{n\to\infty} \sigma_0\sigma_1\cdots\sigma_n(a^\infty)\), see, e.g., [\textit{N. Pytheas Fogg} (ed.) et al., Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794. Berlin: Springer (2002; Zbl 1014.11015)]. The \(S\)-adic conjecture is the existence of a condition \(C\) such that a sequence has a block-complexity in \(O(k)\) if and only if it is an \(S\)-adic sequence satisfying \(C\). Examples of \(S\)-adic sequences for some \(S\) are automatic sequences and fixed points of primitive morphisms. The author proves that if a sequence is aperiodic, uniformly recurrent, and with block complexity \(O(k)\), then it is \(S\)-adic, improving a result due to \textit{S. Ferenczi} [Ergodic Theory Dyn. Syst. 16, No. 4, 663--682 (1996; Zbl 0858.68051)].