کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436140 | 689974 | 2015 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 243–251