A k-ary n-cube is a graph with kn vertices, each associated to a word of length n over an alphabet of cardinality k. The subgraph obtained deleting those vertices which contain a given k-ary word f as a factor is here introduced and called the k-ary n-cube avoiding f. When, for any n, such a subgraph is isometric to the cube, the word f is said isometric. In the binary case, isometric words can be equivalently defined, independently from hypercubes. A binary word f is isometric if and only if it is good, i.e., for any pair of f-free words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only f-free words. These two approaches are here considered in the case of a k-ary alphabet, showing that they are still coincident for k= 3, but they are not from k= 4 on. Bad words are then characterized in terms of their overlaps with errors. Further properties are obtained on non-isometric words and their index, in the case of a quaternary alphabet.

Anselmo M., Flores M., Madonia M. (2021). Quaternary n-cubes and Isometric Words. In T. Lecroq, S. Puzynina (a cura di), Combinatorics on Words 13th International Conference, WORDS 2021, Rouen, France, September 13–17, 2021, Proceedings (pp. 27-39). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-85088-3_3].

### Quaternary n-cubes and Isometric Words

#### Abstract

A k-ary n-cube is a graph with kn vertices, each associated to a word of length n over an alphabet of cardinality k. The subgraph obtained deleting those vertices which contain a given k-ary word f as a factor is here introduced and called the k-ary n-cube avoiding f. When, for any n, such a subgraph is isometric to the cube, the word f is said isometric. In the binary case, isometric words can be equivalently defined, independently from hypercubes. A binary word f is isometric if and only if it is good, i.e., for any pair of f-free words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only f-free words. These two approaches are here considered in the case of a k-ary alphabet, showing that they are still coincident for k= 3, but they are not from k= 4 on. Bad words are then characterized in terms of their overlaps with errors. Further properties are obtained on non-isometric words and their index, in the case of a quaternary alphabet.
##### Scheda breve Scheda completa Scheda completa (DC)
6-set-2021
Settore INF/01 - Informatica
978-3-030-85088-3
Anselmo M., Flores M., Madonia M. (2021). Quaternary n-cubes and Isometric Words. In T. Lecroq, S. Puzynina (a cura di), Combinatorics on Words 13th International Conference, WORDS 2021, Rouen, France, September 13–17, 2021, Proceedings (pp. 27-39). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-85088-3_3].
File in questo prodotto:
File
978-3-030-85088-3.pdf

Solo gestori archvio

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