×

Words whose complexity satisfies lim \(\frac{p(n)}{n} = 1\). (English) Zbl 1058.68083

Summary: We study the infinite words such that lim\(_n\) \(p(n)/n=1\), by using the Rauzy graphs. We show that the infinite evolution of the graphs of these infinite words can be characterized by a rather simple condition, which ensures that the graphs with more than one right special factor appear rarely, so that makes the complexity very small.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberkane, A., Suites de complexité inférieure à \(2n\), Bull. Belg. Math. Soc., 8, 161-180 (2001) · Zbl 0994.68099
[2] Allouche, J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc., 1, 133-143 (1994) · Zbl 0803.68094
[3] Arnoux, P.; Rauzy, G., Représentation géométrique des suites de complexité \(2n+1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[4] Berstel, J.; Séébold, P., Morphismes de Sturm, Bull. Belg. Math. Soc., 1, 175-189 (1994) · Zbl 0803.68095
[5] Coven, E. M.; Hedlund, G. A., Sequences with minimal block growth, Math. Systems Theory, 7, 138-153 (1973) · Zbl 0256.54028
[6] A. Heinis, Arithmetics and combinatorics of words of low complexity, Ph.D. Thesis, University of Leiden, 2001.; A. Heinis, Arithmetics and combinatorics of words of low complexity, Ph.D. Thesis, University of Leiden, 2001. · Zbl 1136.68302
[7] Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90 (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1001.68093
[8] Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[9] Morse, M.; Hedlund, G. A., Symbolic dynamics IISturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[10] Paul, M. E., Minimal symbolic flows having minimal block growth, Math. Systems Theory, 8, 309-315 (1975) · Zbl 0306.54056
[11] G. Rauzy, Suites à termes dans un alphabet fini, Sém. Théo. Nombres Bordeaux (1982-1983) 25.01-25.16.; G. Rauzy, Suites à termes dans un alphabet fini, Sém. Théo. Nombres Bordeaux (1982-1983) 25.01-25.16. · Zbl 0547.10048
[12] Rote, G., Sequences with subword complexity \(2n\), J. Number Theory, 46, 196-213 (1994) · Zbl 0804.11023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.