Characterization of Isometric Words based on Swap and Mismatch Distance
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, Sabrina Mantaci · International Journal of Foundations of Computer Science · 2025
In this paper we consider an edit distance with swap and mismatch operations, called tilde-distance, and introduce the corresponding definition of tilde-isometric word. Isometric words are classically defined with respect to Hamming distance and combine the notion of edit distance with the property that a word does not appear as factor in other words. A word [Formula: see text] is said tilde-isometric if, for any pair of [Formula: see text]-free words [Formula: see text] and [Formula: see text], there exists a minimal transformation from [Formula: see text] to [Formula: see text] via the related edit operations such that all the intermediate words are also [Formula: see text]-free. This new setting is here studied giving a full characterization of the tilde-isometric words in terms of overlaps with errors.