Reference : Do balanced words have a short period? |

Scientific journals : Article | |||

Physical, chemical, mathematical & earth Sciences : Mathematics | |||

http://hdl.handle.net/2268/230109 | |||

Do balanced words have a short period? | |

English | |

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 [] | |

In press | |

Theoretical Computer Science | |

Elsevier | |

Yes (verified by ORBi) | |

International | |

0304-3975 | |

Netherlands | |

[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 | |

Researchers | |

http://hdl.handle.net/2268/230109 |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.