On the product of balanced sequences
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 131-145.

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.

DOI : https://doi.org/10.1051/ita/2011116
Classification : 68R15
Mots clés : 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},
zbl = {1247.68213},
mrnumber = {2904966},
language = {en},
url = {http://www.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
DA  - 2012///
SP  - 131
EP  - 145
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011116/
UR  - https://zbmath.org/?q=an%3A1247.68213
UR  - https://www.ams.org/mathscinet-getitem?mr=2904966
UR  - https://doi.org/10.1051/ita/2011116
DO  - 10.1051/ita/2011116
LA  - en
ID  - ITA_2012__46_1_131_0
ER  - 
Restivo, Antonio; Rosone, Giovanna. On the product of balanced sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 131-145. doi : 10.1051/ita/2011116. http://www.numdam.org/articles/10.1051/ita/2011116/

[1] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing. J. ACM 47 (2000) 752-775. | MR 1866176

[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 Bordeaux 13 (2001) 371-394. | Numdam | MR 1879664 | Zbl 1038.37010

[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). | MR 1469998

[4] S. Ferenczi and C. Mauduit, Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR 1486494 | Zbl 0895.11029

[5] A.S. Fraenkel, Complementing and exactly covering sequences. J. Combin. Theory Ser. A 14 (1973) 8-20. | MR 309770 | Zbl 0257.05023

[6] P. Hubert, Suites équilibrées (french). Theor. Comput. Sci. 242 (2000) 91-108. | MR 1769142 | Zbl 0944.68149

[7] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). | MR 1905123 | Zbl 1221.68183

[8] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745

[9] R.N. Risley and L.Q. Zamboni, A generalization of sturmian sequences : combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR 1785413 | Zbl 0953.11007

[10] P.V. Salimov, On uniform recurrence of a direct product. Discrete Math. Theoret. Comput. Sci. 12 (2010) 1-8. | MR 2760331 | Zbl 1286.68377

[11] L. Vuillon, Balanced words. Bull. Belg. Math. Soc. 10 (2003) 787-805. | MR 2073026 | Zbl 1070.68129

Cité par Sources :