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 : In \cite{KolpakovKucherovMFCS97}, a notion of minimal proportion (density) of one letter in $n$-th power-free binary words has been introduced and some of its properties have been proved. In this paper, we proceed with this study and substantially extend some of these results. 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})$ refining the estimate from \cite{KolpakovKucherovMFCS97}. Following \cite{KolpakovKucherovMFCS97}, we also consider a natural generalization of $n$-th power-free words to $x$-th power-free words for real argument $x$. We prove that the minimal proportion of one letter in $x$-th power-free binary words, considered as a function of $x$, is discontinuous at all integer points $n\geq 3$. Finally, we give an estimate of the size of the jumps.
Type de document :
Communication dans un congrès
Lubos Brim, Jozef Gruska and Jiri Zlatuska. 23rd International Symposium on Mathematical Foundations of Computer Science - MFCS'98, 1998, Brno/Czech Republic, Springer Verlag, 1450, pp.683-692, 1998, Lecture Notes in Computer Science. 〈10.1007/BFb0055819〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00098692
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:17:16
Dernière modification le : mardi 6 mars 2018 - 17:40:58
Document(s) archivé(s) le : mercredi 29 mars 2017 - 12:34:16

Fichiers

Identifiants

Collections

Citation

Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov. On repetition-free binary words of minimal density. Lubos Brim, Jozef Gruska and Jiri Zlatuska. 23rd International Symposium on Mathematical Foundations of Computer Science - MFCS'98, 1998, Brno/Czech Republic, Springer Verlag, 1450, pp.683-692, 1998, Lecture Notes in Computer Science. 〈10.1007/BFb0055819〉. 〈inria-00098692〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

34