×

The characterization of \(N\)-écritures and applications to the study of sequences of finally \(n+c^{st}\) complexity. (Caractérisation des \(N\)-écritures et application à l’étude des suites de complexité ultimement n+c\(^{ste}\).) (French) Zbl 0913.68163

Summary: Nous appelons \(N\)-écriture la transformation sur les mots qui consiste à faire glisser une fenêtre de taille \(N\) le long d’un mot et à le recoder en associant à chaque nouveau facteur une lettre différente. Nous donnons une caractérisation complète des mots obtenus par cette transformation et proposons une méthode permettant de retrouver un antécédent particulier. Enfin nous appliquons les résultats obtenus pour obtenir une nouvelle description des suites dont le nombre de facteurs de longueur \(n\) est de la forme \(n+c^{ste}\) pour n assez grand. En particulier, nous explicitons les liens existant entre ces suites et les suites sturmiennes.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alessandri, P., Codages de rotations et basses complexités, (Thèse de Doctorat (1996), Université d’Aix-Marseille Il)
[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 de suites de complexité \(2n + 1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[4] J. Berstel, Recent results in sturmian words, DLT’95.; J. Berstel, Recent results in sturmian words, DLT’95. · Zbl 1096.68689
[5] Cassaigne, J., Complexité et facteurs spéciaux, Bull. Belg. Soc. Math., 4, 67-88 (1997) · Zbl 0921.68065
[6] Ferenczi, S., Systems of finite rank, (Colloquium Mathematicum, 73 (1997)), 35-65 · Zbl 0883.28014
[7] Ferenczi, S.; Mauduit, C., Transcendence of numbers with a low complexity expansion, (preprint de I’I.M.L. (1995)) · Zbl 0895.11029
[8] Hedlund, G. A.; Morse, M., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[9] Hedlund, G. A.; Morse, M., Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., 62, 287-306 (1940) · JFM 66.0188.03
[10] Mossé, B., Notions de reconnaissabilité pour les substitutions et complexité de suites automatiques, Bull. Soc. Math. France, 124, 101-108 (1996)
[11] Queffélec, M., Substitution Dynamical System — Spectral Analysis, (Lecture Notes in Mathematics, vol. 1294 (1987), Springer: Springer Berlin) · Zbl 0642.28013
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.