Article (Scientific journals)
Do balanced words have a short period?
Brauner, Nadia; Crama, Yves; Delaporte, Etienne et al.
2019In Theoretical Computer Science, 793, p. 169-180
Peer Reviewed verified by ORBi
 

Files


Full Text
Balanced words Dec 2018.pdf
Author preprint (356.31 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
balanced words; congruence words; exact covering systems; constant gap sequences; Graham-Hubert theorem; Fraenkel's conjecture; m-balanced words
Abstract :
[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).
Research center :
QuantOM - HEC
Disciplines :
Mathematics
Author, co-author :
Brauner, Nadia
Crama, Yves  ;  Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Delaporte, Etienne
Jost, Vincent
Libralesso, Luc
Language :
English
Title :
Do balanced words have a short period?
Publication date :
2019
Journal title :
Theoretical Computer Science
ISSN :
0304-3975
Publisher :
Elsevier, Netherlands
Volume :
793
Pages :
169-180
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 12 December 2018

Statistics


Number of views
78 (9 by ULiège)
Number of downloads
53 (3 by ULiège)

Scopus citations®
 
1
Scopus citations®
without self-citations
1
OpenCitations
 
1

Bibliography


Similar publications



Contact ORBi