# zbMATH — the first resource for mathematics

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.].

##### MSC:
 68Q45 Formal languages and automata 68R15 Combinatorics on words
##### Keywords:
primitive substitutions; return words; minimal sequences
Full Text:
##### References:
  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  Béal, M.P., Codage symbolique, (1993), Masson Paris  Berstel, J., Mots sans carrés et morphismes itérés, Discrete math., 29, 235-244, (1979) · Zbl 0444.20050  Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506  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  Cobham, A., Uniform tag sequences, Math. systems theory, 6, 164-192, (1972) · Zbl 0253.02029  Denker, M.; Grillenberger, C.; Sigmund, K., Ergodic theory on compact spaces, () · Zbl 0328.28008  Eilenberg, S., ()  Fabre, S., Substitutions et indépendance des systèmes de numération, ()  Mossé, B., Puissances de mots et reconnaissabilité des points fixes d’une substitution, Theoret. comput. sci., 99, 327-334, (1992) · Zbl 0763.68049  Petersen, K., Ergodic theory, (1995), Cambridge University Press Cambridge  Queffélec, M., Substitution dynamical systems-spectral analysis, () · Zbl 0642.28013  Rozenberg, G.; Salomaa, S., The book of L, (1986), 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.