Complexity of infinite words associated with beta-expansions

Frougny, Christiane¹ ; Masáková, Zuzana ; Pelantová, Edita

¹ Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 2, pp. 163-185.

Résumé

We study the complexity of the infinite word $u_{\beta }$ associated with the Rényi expansion of $1$ in an irrational base $\beta >1$. When $\beta$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ\left(n\right)=n+1$. For $\beta$ such that $d_{\beta }\left(1\right)=t_1{t}_2\cdots t_m$ is finite we provide a simple description of the structure of special factors of the word $u_{\beta }$. When $t_m=1$ we show that $ℂ\left(n\right)=(m-1)n+1$. In the cases when $t_1=t_2=\cdots =t_{m-1}$ or $t_1>max\{t_2,\cdots ,t_{m-1}\}$ we show that the first difference of the complexity function $ℂ(n+1)-ℂ\left(n\right)$ takes value in $\{m-1,m\}$ for every $n$, and consequently we determine the complexity of $u_{\beta }$. We show that $u_{\beta }$ is an Arnoux-Rauzy sequence if and only if $d_{\beta }\left(1\right)=tt\cdots t1$. On the example of $\beta =1+2cos(2\pi /7)$, solution of $X^3=2X^2+X-1$, we illustrate that the structure of special factors is more complicated for $d_{\beta }\left(1\right)$ infinite eventually periodic. The complexity for this word is equal to $2n+1$.

Détail

DOI : 10.1051/ita:2004009

Classification : 11A63, 11A67, 37B10, 68R15
Mots-clés : beta-expansions, complexity of infinite words