کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436140 689974 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solution to a conjecture on words that are bad and 2-isometric
ترجمه فارسی عنوان
راه حل برای فرض بر روی کلمات که بد و 2-ایزومتریک ؟؟
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let f be a finite binary word. Then a binary word u is called f-free if it contains no f as a factor. The 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. Such a process is called an f-free transformation of u to v. The word f is called good if it is d  -good for all d≥1d≥1, it is called bad otherwise. The word f is s-isometric if for any binary words u and v of the same length that differ in s bits there is an f-free transformation of u to v  . Ilić, Klavžar and Rho constructed an infinite family of bad 2-isometric words of the form f=12r−1012r−1012r+1f=12r−1012r−1012r+1 for all r≥0r≥0. They conjectured that the words from this family are all the words that are bad and 2-isometric among those with exactly two 0s. In this paper we show that this conjecture is not true and prove that f   is a bad 2-isometric word that contains exactly two 0s if and only if f=1r01r012r+2f=1r01r012r+2 (or its reverse) for some r≥0r≥0. We also list all of the good words that contain exactly two 0s.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 243–251
نویسندگان
, ,