Special factors of automatic sequences. (English) Zbl 0856.11012

The author defines a special factor \(v\) of an infinite sequence \(u\) on a finite alphabet \(A\) to be a finite factor (subblock) of \(u\) such that, for each letter \(a\in A\), the word \(va\) is also a factor of \(u\). Such words are sometimes called extendable, but note that a more general definition only assumes that \(va\) is a factor for at least one letter \(a\) [see for example: J. Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. (to appear)].
In order to study the special factors of infinite fixed points of morphisms, the author introduces the notion of rythmical word (essentially a word that is the “unique” image of another word by the morphism). Note that a recent paper by B. Mossé [Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. Fr. 124, 329-346 (1996; Zbl 0855.68072)] gives complementary results.


11B85 Automata sequences
68R15 Combinatorics on words


Zbl 0855.68072
Full Text: DOI


[1] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n + l\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[2] Berstel, J., (Mots de Fibonacci: Séminaire d’Informatique Théorique (1980:1981), LITP Université Paris), 57-78, VI et VII Année
[3] Brlek, S., Enumeration of factors in Thue-Morse word, Discrete Appl. Math., 24, 83-96 (1989) · Zbl 0683.20045
[4] Christol, G.; Kamac, T.; Mendes-France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[5] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[6] De Lucas, A.; Varricchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem of semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050
[7] Gottschalk, W. H.; Hedlung, G. A., Topological Dynamics, (Amer Math. Soc. Colloq. Publ., Vol. 36 (1968), AMSE: AMSE Providence, RI) · Zbl 0067.15204
[8] Rauzy, G., Suites à termes dans un alphabet fini, Sém. Théorie Nombres Bodeaux Exp., 35, 1-16 (1982-1983) · Zbl 0547.10048
[9] Tapsoba, T., Automates calculant la complexité de suites automatiques, J. Théorie Nombres Bordeaux, 6, 127-134 (1994) · Zbl 0815.11015
[10] Thue, A., Uber unendliche zeichenreihen, Norske Vid. Selsk. Skr. I. Math. Nat. Kl. Christiana, 7, 1-22 (1906) · JFM 37.0066.17
[11] Thue, A., Uber die gegenseitige lage gleicher teile genvisser zeichenreihen, Norske Vid. Selsk. Skr., I. Math. Nat. Kl, Christiana, 1, 1-67 (1912) · JFM 44.0462.01
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.