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.
Keywords: infinite sequences, Sturmian words, balance, product
@article{ITA_2012__46_1_131_0, author = {Restivo, Antonio and Rosone, Giovanna}, title = {On the product of balanced sequences}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {131--145}, publisher = {EDP-Sciences}, volume = {46}, number = {1}, year = {2012}, doi = {10.1051/ita/2011116}, mrnumber = {2904966}, zbl = {1247.68213}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2011116/} }
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 SP - 131 EP - 145 VL - 46 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011116/ DO - 10.1051/ita/2011116 LA - en ID - ITA_2012__46_1_131_0 ER -
%0 Journal Article %A Restivo, Antonio %A Rosone, Giovanna %T On the product of balanced sequences %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 131-145 %V 46 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011116/ %R 10.1051/ita/2011116 %G en %F ITA_2012__46_1_131_0
Restivo, Antonio; Rosone, Giovanna. On the product of balanced sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 46 (2012) no. 1, pp. 131-145. doi : 10.1051/ita/2011116. http://archive.numdam.org/articles/10.1051/ita/2011116/
[1] Balanced sequences and optimal routing. J. ACM 47 (2000) 752-775. | MR
, and ,[2] Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Théor. Nombres Bordeaux 13 (2001) 371-394. | Numdam | MR | Zbl
, and ,[3] Combinatorics of words, in G. Rozenberg and A. Salomaa eds., Handbook of Formal Language Theory 1. Springer-Verlag, Berlin (1997). | MR
and ,[4] Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR | Zbl
and ,[5] Complementing and exactly covering sequences. J. Combin. Theory Ser. A 14 (1973) 8-20. | MR | Zbl
,[6] Suites équilibrées (french). Theor. Comput. Sci. 242 (2000) 91-108. | MR | Zbl
,[7] Algebraic Combinatorics on Words. Cambridge University Press (2002). | MR | Zbl
,[8] Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM | MR
and ,[9] A generalization of sturmian sequences : combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR | Zbl
and ,[10] On uniform recurrence of a direct product. Discrete Math. Theoret. Comput. Sci. 12 (2010) 1-8. | MR | Zbl
,[11] Balanced words. Bull. Belg. Math. Soc. 10 (2003) 787-805. | MR | Zbl
,Cited by Sources: