On repetition-free binary words of minimal density

Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

We study the minimal proportion (density) of one letter in nth power-free binary words. First, we introduce and analyse a general notion of minimal letter density for any infinite set of words which does not contain a specified set of "prohibited" subwords. We then prove that for nth power-free binary words the density function is 1/n + 1/n3 + 1/n4 + script O sign(1/n5). We also consider a generalization of nth power-free words for fractional powers (exponents): a word is xth 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 xth power-free binary words as a function of x and prove, in particular, that this function is discontinuous at 7/3 as well as at all integer points n ≥ 3. Finally, we give an estimate of the size of the jumps.

Original languageEnglish
Pages (from-to)161-175
Number of pages15
JournalTheoretical Computer Science
Volume218
Issue number1
DOIs
Publication statusPublished - 28 Apr 1999
Externally publishedYes

Keywords

  • Exponent
  • Minimal density
  • Power-free words
  • Unavoidable patterns

Fingerprint

Dive into the research topics of 'On repetition-free binary words of minimal density'. Together they form a unique fingerprint.

Cite this