A characterization of substitutive sequences using return words. (English) Zbl 0895.68087

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 [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 [F. Durand, Theory Comput. Syst. 31, 169-185 (1998)]and the second one concerns dimension groups of Bratelli diagrams [F. Durand, B. Host and C. Skau, “Substitutions , Bratelli diagrams and dimension groups”, to appear in Ergod. Theory Dyn. Syst.].


68Q45 Formal languages and automata
68R15 Combinatorics on words


Zbl 0253.02029
Full Text: DOI arXiv


[1] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[2] Béal, M. P., Codage Symbolique (1993), Masson: Masson Paris
[3] Berstel, J., Mots sans carrés et morphismes itérés, Discrete Math., 29, 235-244 (1979) · Zbl 0444.20050
[4] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[5] Christol, G.; Kamae, T.; Mendes-France, M.; Rauzy, G., Suites Algébriques et Substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[6] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[7] Denker, M.; Grillenberger, C.; Sigmund, K., Ergodic Theory on Compact Spaces, (Lecture Notes in Mathematics, Vol. 527 (1976), Springer: Springer New York) · Zbl 0328.28008
[8] Eilenberg, S., (Automata, Languages and Machines, vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[9] Fabre, S., Substitutions et indépendance des systèmes de numération, (Thesis, II (1992), University of Aix-Marseille)
[10] Mossé, B., Puissances de mots et reconnaissabilité des points fixes d’une substitution, Theoret. Comput. Sci., 99, 327-334 (1992) · Zbl 0763.68049
[11] Petersen, K., Ergodic Theory (1995), Cambridge University Press: Cambridge University Press Cambridge
[12] Queffélec, M., Substitution Dynamical Systems-Spectral Analysis, (Lecture Notes in Mathematics, Vol. 1294 (1987), Springer: Springer Berlin) · Zbl 0642.28013
[13] Rozenberg, G.; Salomaa, S., The Book of L (1986), Springer: Springer Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.