On the conjectures of Rauzy and Shallit for infinite words
Jean-Paul Allouche; Mireille Bousquet-Mélou
Commentationes Mathematicae Universitatis Carolinae (1995)
- Volume: 36, Issue: 4, page 705-711
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topAllouche, Jean-Paul, and Bousquet-Mélou, Mireille. "On the conjectures of Rauzy and Shallit for infinite words." Commentationes Mathematicae Universitatis Carolinae 36.4 (1995): 705-711. <http://eudml.org/doc/247757>.
@article{Allouche1995,
abstract = {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.},
author = {Allouche, Jean-Paul, Bousquet-Mélou, Mireille},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {combinatorics on words; recurrence function; Sturmian sequences; infinite words; Shallit's conjecture; Rauzy's conjecture; combinatorics on words; length of the longest suffix; recurrence function; length of the shortest prefix},
language = {eng},
number = {4},
pages = {705-711},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On the conjectures of Rauzy and Shallit for infinite words},
url = {http://eudml.org/doc/247757},
volume = {36},
year = {1995},
}
TY - JOUR
AU - Allouche, Jean-Paul
AU - Bousquet-Mélou, Mireille
TI - On the conjectures of Rauzy and Shallit for infinite words
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1995
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 36
IS - 4
SP - 705
EP - 711
AB - 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.
LA - eng
KW - combinatorics on words; recurrence function; Sturmian sequences; infinite words; Shallit's conjecture; Rauzy's conjecture; combinatorics on words; length of the longest suffix; recurrence function; length of the shortest prefix
UR - http://eudml.org/doc/247757
ER -
References
top- Allouche J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc. 1 (1994), 133-143. (1994) Zbl0803.68094MR1318964
- Coven E.M., Hedlund G.A., Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138-153. (1973) Zbl0256.54028MR0322838
- 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) Zbl0019.33502MR1507944
- Morse M., Hedlund G.A., Symbolic dynamics II, Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42. (1940) Zbl0022.34003MR0000745
- 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. Zbl0959.11015MR1453865
- 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) Zbl0547.10048MR0750326
- 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) MR1288529
- Shallit J., Breitbart Y., Automaticity I: properties of a measure of decriptional complexity, preprint, 1994. MR1409007
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.