On the product of balanced sequences

Antonio Restivo; Giovanna Rosone

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 1, page 131-145
  • ISSN: 0988-3754

Abstract

top
The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the interest of the notion of product in the study of balanced sequences.

How to cite

top

Restivo, Antonio, and Rosone, Giovanna. "On the product of balanced sequences." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.1 (2012): 131-145. <http://eudml.org/doc/273085>.

@article{Restivo2012,
abstract = {The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the interest of the notion of product in the study of balanced sequences.},
author = {Restivo, Antonio, Rosone, Giovanna},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {infinite sequences; Sturmian words; balance; product},
language = {eng},
number = {1},
pages = {131-145},
publisher = {EDP-Sciences},
title = {On the product of balanced sequences},
url = {http://eudml.org/doc/273085},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Restivo, Antonio
AU - Rosone, Giovanna
TI - On the product of balanced sequences
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2012
PB - EDP-Sciences
VL - 46
IS - 1
SP - 131
EP - 145
AB - The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the interest of the notion of product in the study of balanced sequences.
LA - eng
KW - infinite sequences; Sturmian words; balance; product
UR - http://eudml.org/doc/273085
ER -

References

top
  1. [1] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing. J. ACM47 (2000) 752–775. Zbl1327.68180MR1866176
  2. [2] N. Chekhova, P. Hubert and A. Messaoudi, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Théor. Nombres Bordeaux13 (2001) 371–394. Zbl1038.37010MR1879664
  3. [3] C. Choffrut and J. Karhumaki, Combinatorics of words, in G. Rozenberg and A. Salomaa eds., Handbook of Formal Language Theory 1. Springer-Verlag, Berlin (1997). MR1469998
  4. [4] S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion. J. Number Theory67 (1997) 146–161. Zbl0895.11029MR1486494
  5. [5] A.S. Fraenkel, Complementing and exactly covering sequences. J. Combin. Theory Ser. A14 (1973) 8–20. Zbl0257.05023MR309770
  6. [6] P. Hubert, Suites équilibrées (french). Theor. Comput. Sci.242 (2000) 91–108. Zbl0944.68149MR1769142
  7. [7] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). Zbl1221.68183MR1905123
  8. [8] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. Zbl0022.34003MR745JFM66.0188.03
  9. [9] R.N. Risley and L.Q. Zamboni, A generalization of sturmian sequences : combinatorial structure and transcendence. Acta Arith.95 (2000) 167–184. Zbl0953.11007MR1785413
  10. [10] P.V. Salimov, On uniform recurrence of a direct product. Discrete Math. Theoret. Comput. Sci.12 (2010) 1–8. Zbl1286.68377MR2760331
  11. [11] L. Vuillon, Balanced words. Bull. Belg. Math. Soc.10 (2003) 787–805. Zbl1070.68129MR2073026

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.