The hypercube of dimension n is the graph whose vertices are the 2^n binary words of length n, and there is an edge between two of them if they have Hamming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as tilde-distance, and define the tilde-hypercube with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called tilde-isometric words. The subgraphs keep only the vertices that avoid a given tilde-isometric word as a factor. An infinite family of tilde-isometric words is described; they are isometric with respect to the tilde-distance, but not to the Hamming distance. In the case of word 11, the subgraph is called tilde-Fibonacci cube, as a generalization of the classical Fibonacci cube. The tilde-hypercube and the tilde-Fibonacci cube can be recursively defined; the same holds for the number of their edges. This allows an asymptotic estimation of the number of edges in the tilde-Fibonacci cube, in comparison to the total number in the tildehypercube.

Anselmo M., Castiglione G., Flores M., Giammarresi D., Madonia M., Mantaci S. (2023). Hypercubes and Isometric Words Based on Swap and Mismatch Distance. In H. Bordihn, N. Tran, G. Vaszil (a cura di), Descriptional Complexity of Formal Systems. DCFS 2023 (pp. 21-35). Springer [10.1007/978-3-031-34326-1_2].

### Hypercubes and Isometric Words Based on Swap and Mismatch Distance

#### Abstract

The hypercube of dimension n is the graph whose vertices are the 2^n binary words of length n, and there is an edge between two of them if they have Hamming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as tilde-distance, and define the tilde-hypercube with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called tilde-isometric words. The subgraphs keep only the vertices that avoid a given tilde-isometric word as a factor. An infinite family of tilde-isometric words is described; they are isometric with respect to the tilde-distance, but not to the Hamming distance. In the case of word 11, the subgraph is called tilde-Fibonacci cube, as a generalization of the classical Fibonacci cube. The tilde-hypercube and the tilde-Fibonacci cube can be recursively defined; the same holds for the number of their edges. This allows an asymptotic estimation of the number of edges in the tilde-Fibonacci cube, in comparison to the total number in the tildehypercube.
##### Scheda breve Scheda completa Scheda completa (DC) 2023
978-3-031-34325-4
978-3-031-34326-1
Anselmo M., Castiglione G., Flores M., Giammarresi D., Madonia M., Mantaci S. (2023). Hypercubes and Isometric Words Based on Swap and Mismatch Distance. In H. Bordihn, N. Tran, G. Vaszil (a cura di), Descriptional Complexity of Formal Systems. DCFS 2023 (pp. 21-35). Springer [10.1007/978-3-031-34326-1_2].
File in questo prodotto:
File
DCFS23_ACFGMM.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 435.79 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10447/611453`
• ND
• 0
• ND