*-sturmian words and complexity
Journal de Théorie des Nombres de Bordeaux, Tome 15 (2003) no. 3, pp. 767-804.

Nous définissons des notions analogues à la complexité p(n) et aux mots Sturmiens qui sont appelées respectivement *-complexité p * (n) et mots *-Sturmiens. Nous démontrons que la classe des mots *-Sturmiens coïncide avec la classe des mots satisfaisant à p * (n)n+1 et nous déterminons la structure des mots *-Sturmiens. Pour une classe de mots satisfaisant à p * (n)=n+1, nous donnons une formule générale et une borne supérieure pour p(n). En utilisant cette formule générale, nous donnons des formules explicites pour p(n) pour certains mots appartenant à cette classe. En général, p(n) peut prendre des valeurs élevées, à savoir p(n)2 n 1-ϵ pour certains mots *-Sturmiens. Cependant l’entropie topologique de n’importe quel mot *-Sturmien est nulle.

We give analogs of the complexity p(n) and of Sturmian words which are called respectively the *-complexity p * (n) and *-Sturmian words. We show that the class of *-Sturmian words coincides with the class of words satisfying p * (n)n+1, and we determine the structure of *-Sturmian words. For a class of words satisfying p * (n)=n+1, we give a general formula and an upper bound for p(n). Using this general formula, we give explicit formulae for p(n) for some words belonging to this class. In general, p(n) can take large values, namely, p(n)2 n 1-ϵ holds for some *-Sturmian words; however the topological entropy of any *-Sturmian word is zero.

@article{JTNB_2003__15_3_767_0,
     author = {Nakashima, Izumi and Tamura, Jun-Ichi and Yasutomi, Shin-Ichi},
     title = {$\ast $-sturmian words and complexity},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {767--804},
     publisher = {Universit\'e Bordeaux I},
     volume = {15},
     number = {3},
     year = {2003},
     doi = {10.5802/jtnb.426},
     mrnumber = {2142236},
     zbl = {02184624},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.426/}
}
Izumi Nakashima; Jun-Ichi Tamura; Shin-Ichi Yasutomi. $\ast $-sturmian words and complexity. Journal de Théorie des Nombres de Bordeaux, Tome 15 (2003) no. 3, pp. 767-804. doi : 10.5802/jtnb.426. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.426/

[1] P. Arnoux, C. Mauduit, I. Shiokawa, J.-I. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994), 1-12. | Numdam | MR 1259106 | Zbl 0791.58034

[2] P. Arnoux, G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991), 199-215. | Numdam | MR 1116845 | Zbl 0789.28011

[3] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Comm. Math. Phys. 174 (1995), 43-56. | MR 1372799 | Zbl 0839.11006

[4] T.C. Brown, Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull. 36 (1993), 15-21. | MR 1205889 | Zbl 0804.11021

[5] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138-153. | MR 322838 | Zbl 0256.54028

[6] S. Ferenczi, Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1. Bull. Soc. Math. France 123 (1995), 271-292. | Numdam | MR 1340291 | Zbl 0855.28008

[7] S. Ito, S.-I. Yasutomi, On continued fraction, substitutions and characteristic sequences [nx + y] - [(n - 1)x + y]. Japan. J. Math. 16 (1990), 287-306. | MR 1091163 | Zbl 0721.11009

[8] W.F. Lunnon, P.A.B. Pleasants, Characterization of two-distance sequences. J. Austral. Math. Soc. (Ser. A) 53 (1992), 198-218. | MR 1175712 | Zbl 0759.11005

[9] M. Morse, G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938), 815-866. | JFM 64.0798.04 | MR 1507944 | Zbl 0019.33502

[10] M. Morse, G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. | JFM 66.0188.03 | MR 745 | Zbl 0022.34003

[11] I. Nakashima, J.-I. Tamura, S.-I. Yasutomi, Modified complexity and *-Sturmian word. Proc. Japan Acad. (Ser. A) Math. Sci. 75 (1999), 26-28. | MR 1700732 | Zbl 0928.11012

[12] G. Rote, Sequences with subword complexity 2n. J. Number Theory. 46 (1994), 196-213. | MR 1269252 | Zbl 0804.11023

[13] S.-I. Yasutomi, The continued fraction expansion of α with μ(α) = 3. Acta Arith. 84 (1998), 337-374. | Zbl 0967.11024