کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434767 689795 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The index of a binary word
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The index of a binary word
چکیده انگلیسی

A binary word u is f-free if it does not contain f as a factor. A word f is d-good if for any f-free words u and v of length d, v can be obtained from u by complementing one by one the bits of u on which u and v differ, such that all intermediate words are f-free. We say that f is good if it is d-good for any d≥1. A word is bad if it is not good. The index β(f) of f is the smallest integer d such that f is not d-good, so that β(f)<∞ if and only if f is bad.It is proved that β(f)<∣f∣2 holds for any bad word f. In addition, β(f)<2∣f∣ holds for almost all bad words f and it is conjectured that the same holds for all bad words. We construct an infinite family of 2-isometric bad words. It is conjectured that the words of this family are all the words that are bad and 2-isometric among those with exactly two 1s. These conjectures are supported by computer experiments.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 452, 21 September 2012, Pages 100-106