Characterization of Isometric Words based on Swap and Mismatch Distance
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914763880005632 |
|---|---|
| author | Anselmo, M. Castiglione, G. Flores, M. Giammarresi, D. Madonia, M. Mantaci, S. |
| author_facet | Anselmo, M. Castiglione, G. Flores, M. Giammarresi, D. Madonia, M. Mantaci, S. |
| contents | 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 f is said tilde-isometric if, for any pair of f-free words u and v, there exists a transformation from u to v via the related edit operations such that all the intermediate words are also f -free. This new setting is here studied giving a full characterization of the tilde-isometric words in terms of overlaps with errors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13577 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterization of Isometric Words based on Swap and Mismatch Distance Anselmo, M. Castiglione, G. Flores, M. Giammarresi, D. Madonia, M. Mantaci, S. Formal Languages and Automata Theory 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 f is said tilde-isometric if, for any pair of f-free words u and v, there exists a transformation from u to v via the related edit operations such that all the intermediate words are also f -free. This new setting is here studied giving a full characterization of the tilde-isometric words in terms of overlaps with errors. |
| title | Characterization of Isometric Words based on Swap and Mismatch Distance |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2404.13577 |