Special factors of automatic sequences. (English) Zbl 0856.11012

Tapsoba, Théodore

J. Pure Appl. Algebra 108, No. 3, 301-313 (1996).

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.

Reviewer: J.-P.Allouche (Orsay)

MSC:

11B85	Automata sequences
68R15	Combinatorics on words

Keywords:

complexity of a sequence; extendable words; special factors of infinite fixed points of morphisms; rythmical word

Citations:

Zbl 0855.68072

References:

[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