Isometric words combine the notion of edit distance together with properties of words not appearing as factors in other words. An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word f is said isometric with respect to an edit distance if, for any pair of f-free words u and v, there exists a transformation of minimal length from u into v via the related edit operations such that all the intermediate words are also f-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only replacement operations are used), then isometric words are connected with the definitions of isometric subgraphs of hypercubes. We discuss known results and some interesting generalizations and open problems.

Castiglione G., Flores M., Giammarresi D. (2023). Isometric Words and Edit Distance: Main Notions and New Variations. In L. Manzoni, L. Mariot, D.R. Chowdhury (a cura di), Cellular Automata and Discrete Complex Systems 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings (pp. 3-16) [10.1007/978-3-031-42250-8_1].

### Isometric Words and Edit Distance: Main Notions and New Variations

#### Abstract

Isometric words combine the notion of edit distance together with properties of words not appearing as factors in other words. An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word f is said isometric with respect to an edit distance if, for any pair of f-free words u and v, there exists a transformation of minimal length from u into v via the related edit operations such that all the intermediate words are also f-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only replacement operations are used), then isometric words are connected with the definitions of isometric subgraphs of hypercubes. We discuss known results and some interesting generalizations and open problems.
##### Scheda breve Scheda completa Scheda completa (DC)
24-ago-2023
Settore INF/01 - Informatica
978-3-031-42249-2
978-3-031-42250-8
Castiglione G., Flores M., Giammarresi D. (2023). Isometric Words and Edit Distance: Main Notions and New Variations. In L. Manzoni, L. Mariot, D.R. Chowdhury (a cura di), Cellular Automata and Discrete Complex Systems 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings (pp. 3-16) [10.1007/978-3-031-42250-8_1].
File in questo prodotto:
File
978-3-031-42250-8.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 340.98 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10447/618735`