Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438378 | Theoretical Computer Science | 2007 | 5 Pages |
Abstract
We estimate the extremal letter frequency in infinite words over a finite alphabet avoiding some repetitions. For ternary square-free words, we improve the bounds of Tarannikov on the minimal letter frequency, and prove that the maximal letter frequency is . Kolpakov et al. have studied the function ρ such that ρ(x) is the minimal letter frequency in an infinite binary x-free word. In particular, they have shown that ρ is discontinuous at and at every integer at least 3. We answer one of their questions by providing some other points of discontinuity for ρ. Finally, we propose stronger versions of Dejean’s conjecture on repetition threshold in which unequal letter frequencies are required.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics