$*$-sturmian words and complexity

Nakashima, Izumi ; Tamura, Jun-Ichi ; Yasutomi, Shin-Ichi

Journal de théorie des nombres de Bordeaux, Tome 15 (2003) no. 3, pp. 767-804

Abstract (VO)

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

Résumé

Nous définissons des notions analogues à la complexité $p\left(n\right)$ et aux mots Sturmiens qui sont appelées respectivement $*$-complexité $p_{*}\left(n\right)$ et mots $*$-Sturmiens. Nous démontrons que la classe des mots $*$-Sturmiens coïncide avec la classe des mots satisfaisant à $p_{*}\left(n\right)\le n+1$ et nous déterminons la structure des mots $*$-Sturmiens. Pour une classe de mots satisfaisant à $p_{*}\left(n\right)=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\left(n\right)$ pour certains mots appartenant à cette classe. En général, $p\left(n\right)$ peut prendre des valeurs élevées, à savoir $p\left(n\right)\ge 2^{n^{1-ϵ}}$ pour certains mots $*$-Sturmiens. Cependant l’entropie topologique de n’importe quel mot $*$-Sturmien est nulle.