A characterization of substitutive sequences using return words (Q1377710)

The purpose of this paper is to give a characterisation of primitive substitutive sequences by using the notion of return word. Let \(u\) be a non-empty prefix of a minimal (or uniformly recurrent) sequence \(x\). A return word of \(u\) is a word separating two successive occurrences of the word \(u\) in \(x\) (possibly with overlap). By coding the initial sequence \(x\) with these return words, one otains a sequence called derivated sequence, defined on a finite alphabet by minimality and still uniformly recurrent. The main result of this paper is the following: a sequence is substitutive if and only if the set of derivated sequences is finite. The proof of the``only if'' part involves a precise study of primitive matrices: in particular, the lengths of the return words over \(u\) are proved to be proportional to the length of \(u\), and the number of return words of \(u\) is bounded independently of \(u\). This very nice result result is to be compared to Cobham's characterisation of substitutions of constant length [\textit{A. Cobham}, Math. Systems Theory 6, 164-192 (1972; Zbl 0253.02029)]: a sequence \(x\) is generated by a q-substitution (or in other words, is \(q\)-automatic) if and only if its q-kernel (i.e., the set of subsequences \((X_{q^kn+r})_n\), where \(0 \leq r \leq q^k-1\) and \(k \geq 0)\) is finite. Note two recent applications of the study of return words: the first one deals with numeration systems [\textit{F. Durand}, Theory Comput. Syst. 31, 169-185 (1998)]and the second one concerns dimension groups of Bratelli diagrams [\textit{F. Durand, B. Host} and \textit{C. Skau}, ``Substitutions , Bratelli diagrams and dimension groups'', to appear in Ergod. Theory Dyn. Syst.].