Previous |  Up |  Next


Title: On the conjectures of Rauzy and Shallit for infinite words (English)
Author: Allouche, Jean-Paul
Author: Bousquet-Mélou, Mireille
Language: English
Journal: Commentationes Mathematicae Universitatis Carolinae
ISSN: 0010-2628 (print)
ISSN: 1213-7243 (online)
Volume: 36
Issue: 4
Year: 1995
Pages: 705-711
Category: math
Summary: 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. (English)
Keyword: combinatorics on words
Keyword: recurrence function
Keyword: Sturmian sequences
MSC: 11B05
MSC: 11B85
MSC: 68R15
idZBL: Zbl 0859.11019
idMR: MR1378691
Date available: 2009-01-08T18:21:04Z
Last updated: 2012-04-30
Stable URL:
Reference: [1] Allouche J.-P.: Sur la complexité des suites infinies.Bull. Belg. Math. Soc. 1 (1994), 133-143. Zbl 0803.68094, MR 1318964
Reference: [2] Coven E.M., Hedlund G.A.: Sequences with minimal block growth.Math. Systems Theory 7 (1973), 138-153. Zbl 0256.54028, MR 0322838
Reference: [3] Mignosi F., Restivo A., Salemi S.: A periodicity theorem on words and applications.Math. Foundations of Computer Science (1995).
Reference: [4] Morse M., Hedlund G.A.: Symbolic dynamics.Amer. J. Math. 60 (1938), 815-866. Zbl 0019.33502, MR 1507944
Reference: [5] Morse M., Hedlund G.A.: Symbolic dynamics II, Sturmian trajectories.Amer. J. Math. 62 (1940), 1-42. Zbl 0022.34003, MR 0000745
Reference: [6] Mouline J.: Contribution à l'étude de la complexité des suites substitutives.Thèse, Université de Provence (1989).
Reference: [7] Pomerance C., Robson J.M., Shallit J.: Automaticity II: descriptional complexity in the unary case.preprint, 1994. Zbl 0959.11015, MR 1453865
Reference: [8] Rauzy G.: Suites à termes dans un alphabet fini.Sém. de Théorie des Nombres de Bordeaux (1982-1983), 25-01-25-16. Zbl 0547.10048, MR 0750326
Reference: [9] Shallit J., Breitbart Y.: Automaticity I: properties of a measure of decriptional 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. MR 1288529
Reference: [10] Shallit J., Breitbart Y.: Automaticity I: properties of a measure of decriptional complexity.preprint, 1994. MR 1409007


Files Size Format View
CommentatMathUnivCarolRetro_36-1995-4_8.pdf 191.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo