| 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:
|
http://hdl.handle.net/10338.dmlcz/118797 |
| . |
| 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 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 |
| Reference:
|
[10] Shallit J., Breitbart Y.: Automaticity I: properties of a measure of decriptional complexity.preprint, 1994. MR 1409007 |
| . |
