Article ID Journal Published Year Pages File Type
438378 Theoretical Computer Science 2007 5 Pages PDF
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