A transformation between a pair of binary words.u and . v of the same length and Hamming distance.d is a sequence o f w ords .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 wor d. f, i f .f is absent in all .wi, i.e. if .f is not a factor of an y.wi. A word .f is good if there exists an .f -free transformation between any pair o f .f -free words of same length. Good words have been completely characterized using combinatorial methods on words. A word.f is a minimal absent wor d for .w if .f is an absent word in .w but all its proper factors occur i n . w. W e consider .f -free transformations between pairs of words. u and . v for whic h .f is a minimal absent word and study how the prop erty 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 M.P. Béal, P. Caron (a cura di), evelopments in Language Theory 30th International Conference, DLT 2026, Rouen, France, June 30 – July 3, 2026, Proceedings (pp. 252-265) [10.1007/978-3-032-28404-4_19].
Transformations between Minimally f-free Words
Castiglione G.;Mantaci S.
2026-01-01
Abstract
A transformation between a pair of binary words.u and . v of the same length and Hamming distance.d is a sequence o f w ords .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 wor d. f, i f .f is absent in all .wi, i.e. if .f is not a factor of an y.wi. A word .f is good if there exists an .f -free transformation between any pair o f .f -free words of same length. Good words have been completely characterized using combinatorial methods on words. A word.f is a minimal absent wor d for .w if .f is an absent word in .w but all its proper factors occur i n . w. W e consider .f -free transformations between pairs of words. u and . v for whic h .f is a minimal absent word and study how the prop erty of including the proper factors of.f can be maintained in the intermediate words of the transformation.
| File | Dimensione | Formato | |
|---|---|---|---|
|
DLT_26_Transformations.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
840.17 kB
Formato
Adobe PDF
|
840.17 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
