. 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.
30th International Conference on Developments in Language Theory, DLT 2026
Rouen (France)
2026
30
Rilevanza internazionale
contributo
2026
lug-2026
Settore INFO-01/A - Informatica
English
Good words
Hamming distance
Minimal Absent Words (MAW)
Transformations of words
Intervento a convegno
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].
Anselmo, M; Castiglione, G; Flores, M; Giammarresi, D; Madonia, M; Mantaci, S
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/473416
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact