Complexity of infinite words associated with beta-expansions

Frougny, Christiane, Masáková, Zuzana, and Pelantová, Edita. "Complexity of infinite words associated with beta-expansions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.2 (2004): 163-185. <http://eudml.org/doc/244788>.

@article{Frougny2004,
abstract = {We study the complexity of the infinite word $u_\beta $ associated with the Rényi expansion of $1$ in an irrational base $\beta &gt;1$. When $\beta $ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $\mathbb \{C\}(n)=n+1$. For $\beta $ such that $d_\beta (1)=t_1t_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 $\mathbb \{C\}(n)=(m-1)n+1$. In the cases when $t_1=t_2=\cdots =t_\{m-1\}$ or $t_1&gt;\max \lbrace t_2,\dots ,t_\{m-1\}\rbrace $ we show that the first difference of the complexity function $\mathbb \{C\}(n+1)-\mathbb \{C\}(n)$ takes value in $\lbrace m-1,m\rbrace $ 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 (1)=t\,t\cdots \,t\,1$. On the example of $\beta =1+2\cos (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 (1)$ infinite eventually periodic. The complexity for this word is equal to $2n+1$.},
affiliation = {Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8},
author = {Frougny, Christiane, Masáková, Zuzana, Pelantová, Edita},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {beta-expansions; complexity of infinite words},
language = {eng},
number = {2},
pages = {163-185},
publisher = {EDP-Sciences},
title = {Complexity of infinite words associated with beta-expansions},
url = {http://eudml.org/doc/244788},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Frougny, Christiane
AU - Masáková, Zuzana
AU - Pelantová, Edita
TI - Complexity of infinite words associated with beta-expansions
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 2
SP - 163
EP - 185
AB - We study the complexity of the infinite word $u_\beta $ associated with the Rényi expansion of $1$ in an irrational base $\beta &gt;1$. When $\beta $ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $\mathbb {C}(n)=n+1$. For $\beta $ such that $d_\beta (1)=t_1t_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 $\mathbb {C}(n)=(m-1)n+1$. In the cases when $t_1=t_2=\cdots =t_{m-1}$ or $t_1&gt;\max \lbrace t_2,\dots ,t_{m-1}\rbrace $ we show that the first difference of the complexity function $\mathbb {C}(n+1)-\mathbb {C}(n)$ takes value in $\lbrace m-1,m\rbrace $ 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 (1)=t\,t\cdots \,t\,1$. On the example of $\beta =1+2\cos (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 (1)$ infinite eventually periodic. The complexity for this word is equal to $2n+1$.
LA - eng
KW - beta-expansions; complexity of infinite words
UR - http://eudml.org/doc/244788
ER -