Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
combinatorics on words; recurrence function; Sturmian sequences
combinatorics on words; recurrence function; Sturmian sequences
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.
References:
[1] Allouche J.-P.: Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994), 133-143. MR 1318964 | Zbl 0803.68094
[2] Coven E.M., Hedlund G.A.: Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138-153. MR 0322838 | Zbl 0256.54028
[3] Mignosi F., Restivo A., Salemi S.: A periodicity theorem on words and applications. Math. Foundations of Computer Science (1995).
[4] Morse M., Hedlund G.A.: Symbolic dynamics. Amer. J. Math. 60 (1938), 815-866. MR 1507944 | Zbl 0019.33502
[5] Morse M., Hedlund G.A.: Symbolic dynamics II, Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. MR 0000745 | Zbl 0022.34003
[6] Mouline J.: Contribution à l'étude de la complexité des suites substitutives. Thèse, Université de Provence (1989).
[7] Pomerance C., Robson J.M., Shallit J.: Automaticity II: descriptional complexity in the unary case. preprint, 1994. MR 1453865 | Zbl 0959.11015
[8] Rauzy G.: Suites à termes dans un alphabet fini. Sém. de Théorie des Nombres de Bordeaux (1982-1983), 25-01-25-16. MR 0750326 | Zbl 0547.10048
[9] 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. MR 1288529
[10] Shallit J., Breitbart Y.: Automaticity I: properties of a measure of decriptional complexity. preprint, 1994. MR 1409007
Search
Partner of
