Reference : Do balanced words have a short period?
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Do balanced words have a short period?
Brauner, Nadia []
Crama, Yves mailto [Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Delaporte, Etienne []
Jost, Vincent []
Libralesso, Luc []
In press
Theoretical Computer Science
Yes (verified by ORBi)
[en] balanced words ; congruence words ; exact covering systems ; constant gap sequences ; Graham-Hubert theorem ; Fraenkel's conjecture ; m-balanced words
[en] We conjecture that each balanced word on N letters
- either arises from a balanced word on two letters by expanding both letters with a congruence word,
- or is D-periodic with D <= 2^N-1.
Our conjecture arises from extensive numerical experiments. It implies, for any fixed N, the finiteness of the number of balanced words on N letters which do not arise from expanding a balanced word on two letters. It refines a theorem of Graham and Hubert, which states that non-periodic balanced words are congruence expansions of balanced words on two letters. It also relates to Fraenkel's conjecture, which states that for N > 2, every balanced word with distinct densities d_1 > d_2 > ... > d_N satisfies d_i = 2^{N-i} / (2^N-1), since this implies that the word is D-periodic with D= 2^N-1. For N < 7, we provide a tentative list of the density vectors of balanced words which do not arise from expanding a balanced word with fewer letters. We prove that the list is complete for N=4 letters.
We also prove that deleting a letter in a congruence word always produces a balanced word and this construction allows us to further reduce the list of density vectors that remains unexplained. Moreover, we prove that deleting a letter in an m-balanced word produces an (m+1)-balanced word, thus extending and simplifying a result of Sano et al. (2004).
QuantOM - HEC

File(s) associated to this reference

Fulltext file(s):

Open access
Balanced words Dec 2018.pdfAuthor preprint347.96 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.