کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438378 690265 2007 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Letter frequency in infinite repetition-free words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Letter frequency in infinite repetition-free words
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 380, Issue 3, 28 June 2007, Pages 388-392