On the conjectures of Rauzy and Shallit for infinite words
Allouche, Jean-Paul ; Bousquet-Mélou, Mireille
Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995), p. 705-711 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy for infinite words on a finite alphabet. More precisely we show that a Rauzy-like conjecture is equivalent to Shallit's. In passing we correct a misprint in Rauzy's conjecture.

Publié le : 1995-01-01
Classification:  11B05,  11B85,  68R15 
@article{118797,
     author = {Jean-Paul Allouche and Mireille Bousquet-M\'elou},
     title = {On the conjectures of Rauzy and Shallit for infinite words},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {36},
     year = {1995},
     pages = {705-711},
     zbl = {0859.11019},
     mrnumber = {1378691},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118797}
}

Allouche, Jean-Paul; Bousquet-Mélou, Mireille. On the conjectures of Rauzy and Shallit for infinite words. Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995) pp. 705-711. http://gdmltest.u-ga.fr/item/118797/

Allouche J.-P. Sur la complexité des suites infinies, Bull. Belg. Math. Soc. 1 (1994), 133-143. (1994) | MR 1318964 | Zbl 0803.68094

Coven E.M.; Hedlund G.A. Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138-153. (1973) | MR 0322838 | Zbl 0256.54028

Mignosi F.; Restivo A.; Salemi S. A periodicity theorem on words and applications, Math. Foundations of Computer Science (1995).

Morse M.; Hedlund G.A. Symbolic dynamics, Amer. J. Math. 60 (1938), 815-866. (1938) | MR 1507944 | Zbl 0019.33502

Morse M.; Hedlund G.A. Symbolic dynamics II, Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42. (1940) | MR 0000745 | Zbl 0022.34003

Mouline J. Contribution à l'étude de la complexité des suites substitutives, Thèse, Université de Provence (1989). (1989)

Pomerance C.; Robson J.M.; Shallit J. Automaticity II: descriptional complexity in the unary case, preprint, 1994. | MR 1453865 | Zbl 0959.11015

Rauzy G. Suites à termes dans un alphabet fini, Sém. de Théorie des Nombres de Bordeaux (1982-1983), 25-01-25-16. (1982-1983) | MR 0750326 | Zbl 0547.10048

Shallit J.; Breitbart Y. Automaticity I: properties of a measure of decriptional complexity, in: P. Enjalbert, E.W. Mayr, K.W. Wagner editors, STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science (Springer-Verlag) 775 (1994), 619-630. (1994) | MR 1288529

Shallit J.; Breitbart Y. Automaticity I: properties of a measure of decriptional complexity, preprint, 1994. | MR 1409007