On repetition-free binary words of minimal density

Roman Kolpakov Gregory Kucherov 1 Yuri Tarannikov
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the minimal proportion (density) of one letter in $n$-th power-free binary words. First, we introduce and analyse a general notion of minimal letter density for any infinite set of words which don't contain a specified set of ``prohibited'' subwords. We then prove that for $n$-th power-free binary words the density function is $\frac{1}{n}+\frac{1}{n^3}+\frac{1}{n^4}+ {\cal O}(\frac{1}{n^5})$. We also consider a generalization of $n$-th power-free words for fractional powers (exponents): a word is $x$-th power-free for a real $x$, if it does not contain subwords of exponent $x$ or more. We study the minimal proportion of one letter in $x$-th power-free binary words as a function of $x$ and prove, in particular, that this function is discontinuous at $\frac{7}{3}$ as well as at all integer points $n\geq 3$. Finally, we give an estimate of the size of the jumps.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1999, 218 (1), pp.161--175
Liste complète des métadonnées

https://hal.inria.fr/inria-00098854
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:18
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00098854, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov. On repetition-free binary words of minimal density. Theoretical Computer Science, Elsevier, 1999, 218 (1), pp.161--175. 〈inria-00098854〉

Partager

Métriques

Consultations de la notice

93