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 >= 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. Hie, Klavzar and Rho constructed an infinite family of bad 2-isometric words of the form f = 1(2r-1)01(2r-1)01(2r+1) for all r >= 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 = 1(r)01(r)01(2r+2) (or its reverse) for some r >= 0. We also list all of the good words that contain exactly two 0s. (C) 2014 Elsevier B.V. All rights reserved.
展开▼
