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

Complexity of infinite words associated with beta-expansions. (English) Zbl 1104.11013

Theor. Inform. Appl. 38, No. 2, 163-185, corrigendum No. 3, 269-271 (2004).
Summary: 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 \(\mathcal 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 \(\mathcal C(n)=(m-1)n+1\). In the cases when \(t_1=t_2=\cdots=t_{m-1}\) or \(t_1>\max\{t_2,\dots,t_{m-1}\}\) we show that the first difference of the complexity function \(\mathcal C(n+1)-\mathcal C(n)\) 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(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\).
In the corrigendum we add a sufficient condition for validity of Proposition 4.10. This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper use it.

Cited in 1 Review
Cited in 13 Documents

MSC:

11B85 Automata sequences
11A63 Radix representation; digital problems
68R15 Combinatorics on words
37B10 Symbolic dynamics
PDFBibTeX XMLCite
\textit{C. Frougny} et al., Theor. Inform. Appl. 38, No. 2, 163--185, No. 3, 269--271 (2004; Zbl 1104.11013)
Full Text: DOI DOI Numdam Numdam Numdam EuDML

References:

[1] J.-P. Allouche , Sur la complexité des suites infinies . Bull. Belg. Math. Soc. Simon Stevin 1 ( 1994 ) 133 - 143 . Article | MR 1318964 | Zbl 0803.68094 · Zbl 0803.68094
[2] P. Arnoux et 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 · Zbl 0789.28011
[3] J. Berstel , Recent results on extensions of Sturmian words . J. Algebra Comput. 12 ( 2003 ) 371 - 385 . MR 1902372 | Zbl 1007.68141 · Zbl 1007.68141 · doi:10.1142/S021819670200095X
[4] A. Bertrand , Développements en base de Pisot et répartition modulo 1 . C. R. Acad. Sci. Paris 285A ( 1977 ) 419 - 421 . MR 447134 | Zbl 0362.10040 · Zbl 0362.10040
[5] A. Bertrand-Mathis , Comment écrire les nombres entiers dans une base qui n’est pas entière . Acta Math. Acad. Sci. Hungar. 54 ( 1989 ) 237 - 241 . Zbl 0695.10005 · Zbl 0695.10005 · doi:10.1007/BF01952053
[6] J. Cassaigne , Complexité et facteurs spéciaux . Bull. Belg. Math. Soc. Simon Stevin 4 ( 1997 ) 67 - 88 . Article | MR 1440670 | Zbl 0921.68065 · Zbl 0921.68065
[7] J. Cassaigne , S. Ferenczi and L. Zamboni , Imbalances in Arnoux-Rauzy sequences . Ann. Inst. Fourier 50 ( 2000 ) 1265 - 1276 . Numdam | MR 1799745 | Zbl 1004.37008 · Zbl 1004.37008 · doi:10.5802/aif.1792
[8] S. Fabre , Substitutions et \(\beta \)-systèmes de numération . Theoret. Comput. Sci. 137 ( 1995 ) 219 - 236 . MR 1311222 | Zbl 0872.11017 · Zbl 0872.11017 · doi:10.1016/0304-3975(95)91132-A
[9] Ch. Frougny , J.-P. Gazeau and R. Krejcar , Additive and multiplicative properties of point sets based on beta-integers . Theoret. Comput. Sci. 303 ( 2003 ) 491 - 516 . MR 1990778 | Zbl 1036.11034 · Zbl 1036.11034 · doi:10.1016/S0304-3975(02)00503-0
[10] M. Lothaire , Algebraic combinatorics on words . Cambridge University Press ( 2002 ). MR 1905123 | Zbl 1001.68093 · Zbl 1001.68093
[11] W. Parry , On the \(\beta \)-expansions of real numbers . Acta Math. Acad. Sci. Hungar. 11 ( 1960 ) 401 - 416 . MR 142719 | Zbl 0099.28103 · Zbl 0099.28103 · doi:10.1007/BF02020954
[12] J. Patera , Statistics of substitution sequences . On-line computer program, available at http://kmlinux.fjfi.cvut.cz/ patera/SubstWords.cgi [13] A. Rényi , Representations for real numbers and their ergodic properties . Acta Math. Acad. Sci. Hungar. 8 ( 1957 ) 477 - 493 . MR 97374 | Zbl 0079.08901 · Zbl 0079.08901 · doi:10.1007/BF02020331
[13] K. Schmidt , On periodic expansions of Pisot numbers and Salem numbers . Bull. London Math. Soc. 12 ( 1980 ) 269 - 278 . MR 576976 | Zbl 0494.10040 · Zbl 0494.10040 · doi:10.1112/blms/12.4.269
[14] W.P. Thurston , Groups, tilings, and finite state automata . Geometry supercomputer project research report GCG1, University of Minnesota ( 1989 ).
[15] O. Turek , Complexity and balances of the infinite word of \(\beta \)-integers for \(\beta =1 + \sqrt{3}\) , in Proc. of Words’03, Turku. TUCS Publication 27 ( 2003 ) 138 - 148 . Zbl 1040.68090 · Zbl 1040.68090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.