. A transformation between a pair of binary words u and v of the same length and Hamming distance d is a sequence of words w0 = u, w1, w2, . . ., wd = v, such that wi differs from wi+1 only in one position. The transformation is said to be f-free, for a given word f, if f is absent in all wi, i.e. if f is not a factor of any wi. A word f is good if there exists an f-free transformation between any pair of f-free words of same length. Good words have been completely characterized using combinatorial methods on words. A word f is a minimal absent word for w if f is an absent word in w but all its proper factors occur in w. We consider f-free transformations between pairs of words u and v for which f is a minimal absent word and study how the property of including the proper factors of f can be maintained in the intermediate words of the transformation.
Anselmo, M., Castiglione, G., Flores, M., Giammarresi, D., Madonia, M., Mantaci, S. (2026). Transformations between Minimally f-free Words. In Lecture Notes in Computer Science (pp.252-265). Springer [10.1007/978-3-032-28404-4_19].
Transformations between Minimally f-free Words
Dora Giammarresi
;
2026-07-01
Abstract
. A transformation between a pair of binary words u and v of the same length and Hamming distance d is a sequence of words w0 = u, w1, w2, . . ., wd = v, such that wi differs from wi+1 only in one position. The transformation is said to be f-free, for a given word f, if f is absent in all wi, i.e. if f is not a factor of any wi. A word f is good if there exists an f-free transformation between any pair of f-free words of same length. Good words have been completely characterized using combinatorial methods on words. A word f is a minimal absent word for w if f is an absent word in w but all its proper factors occur in w. We consider f-free transformations between pairs of words u and v for which f is a minimal absent word and study how the property of including the proper factors of f can be maintained in the intermediate words of the transformation.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


