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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.