Complexity of infinite words associated with beta-expansions

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

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 38, Issue: 2, page 163-185
  • ISSN: 0988-3754

Abstract

top
We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-1} we show that the first difference of the complexity function C(n + 1) - C(n ) takes value in {m - 1,m} for every n, and consequently we determine the complexity of uβ. We show that uβ is an Arnoux-Rauzy sequence if and only if dβ(1) = tt...t1. On the example of β = 1 + 2cos(2π/7), solution of X3 = 2X2 + X - 1, we illustrate that the structure of special factors is more complicated for dβ(1) infinite eventually periodic. The complexity for this word is equal to 2n+1.

How to cite

top

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

@article{Frougny2010,
abstract = { We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max\{t2,...,tm-1\} we show that the first difference of the complexity function C(n + 1) - C(n ) takes value in \{m - 1,m\} for every n, and consequently we determine the complexity of uβ. We show that uβ is an Arnoux-Rauzy sequence if and only if dβ(1) = tt...t1. On the example of β = 1 + 2cos(2π/7), solution of X3 = 2X2 + X - 1, we illustrate that the structure of special factors is more complicated for dβ(1) infinite eventually periodic. The complexity for this word is equal to 2n+1. },
author = {Frougny, Christiane, Masáková, Zuzana, Pelantová, Edita},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Beta-expansions; complexity of infinite words.},
language = {eng},
month = {3},
number = {2},
pages = {163-185},
publisher = {EDP Sciences},
title = {Complexity of infinite words associated with beta-expansions},
url = {http://eudml.org/doc/92737},
volume = {38},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 38
IS - 2
SP - 163
EP - 185
AB - We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-1} we show that the first difference of the complexity function C(n + 1) - C(n ) takes value in {m - 1,m} for every n, and consequently we determine the complexity of uβ. We show that uβ is an Arnoux-Rauzy sequence if and only if dβ(1) = tt...t1. On the example of β = 1 + 2cos(2π/7), solution of X3 = 2X2 + X - 1, we illustrate that the structure of special factors is more complicated for dβ(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/92737
ER -

References

top
  1. J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 133-143.  
  2. P. Arnoux et G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199-215.  
  3. J. Berstel, Recent results on extensions of Sturmian words. J. Algebra Comput.12 (2003) 371-385.  
  4. A. Bertrand, Développements en base de Pisot et répartition modulo 1. C. R. Acad. Sci. Paris285A (1977) 419-421.  
  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.  
  6. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67-88.  
  7. J. Cassaigne, S. Ferenczi and L. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier50 (2000) 1265-1276.  
  8. S. Fabre, Substitutions et β-systèmes de numération. Theoret. Comput. Sci.137 (1995) 219-236.  
  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.  
  10. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).  
  11. W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960) 401-416.  
  12. J. Patera, Statistics of substitution sequences. On-line computer program, available at  URIhttp://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.  
  14. K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc.12 (1980) 269-278.  
  15. W.P. Thurston, Groups, tilings, and finite state automata. Geometry supercomputer project research report GCG1, University of Minnesota (1989).  
  16. O. Turek, Complexity and balances of the infinite word of β-integers for β = 1 + √3, in Proc. of Words'03, Turku. TUCS Publication 27 (2003) 138-148.  

NotesEmbed ?

top

You must be logged in to post comments.