*-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 = {Izumi Nakashima and Jun-Ichi Tamura and Shin-Ichi Yasutomi},
     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},
     zbl = {1155.68479},
     mrnumber = {2142236},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_2003__15_3_767_0/}
}
TY  - JOUR
AU  - Izumi Nakashima
AU  - Jun-Ichi Tamura
AU  - Shin-Ichi Yasutomi
TI  - $\ast $-sturmian words and complexity
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2003
SP  - 767
EP  - 804
VL  - 15
IS  - 3
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/item/JTNB_2003__15_3_767_0/
LA  - en
ID  - JTNB_2003__15_3_767_0
ER  - 
%0 Journal Article
%A Izumi Nakashima
%A Jun-Ichi Tamura
%A Shin-Ichi Yasutomi
%T $\ast $-sturmian words and complexity
%J Journal de théorie des nombres de Bordeaux
%D 2003
%P 767-804
%V 15
%N 3
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_2003__15_3_767_0/
%G en
%F JTNB_2003__15_3_767_0
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. https://jtnb.centre-mersenne.org/item/JTNB_2003__15_3_767_0/

[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 | Zbl

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

[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 | Zbl

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

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