The k-ary n-cubes are a generalization of the hypercubes to alphabets of cardinality k, with k≥2. More precisely, a k-ary n-cube is a graph with kn vertices associated to the k-ary words of length n. Given a k-ary word f, the k-ary n-cube avoiding f is the subgraph obtained deleting those vertices which contain f as a factor. When such a subgraph is isometric to the cube, for any n≥1, the word f is said isometric. A binary word f is isometric if and only if it is Ham-isometric, i.e., for any pair of f-free binary words u and v, u can be transformed in v by complementing the bits on which they differ and generating only f-free words. The case of a k-ary alphabet, with k≥2, is here investigated. From k≥4, the isometricity in terms of cubes is no longer captured by the Ham-isometricity, but by the Lee-isometricity. Then, Ham-isometric and Lee-isometric k-ary words are characterized in terms of their overlaps with errors. The minimal length of two words which witness the non-isometricity of a word f is called its index. The index of f is bounded in terms of its length and the bounds are shown tight by examples.

Anselmo M., Flores M., Madonia M. (2022). On k-ary n-cubes and isometric words. THEORETICAL COMPUTER SCIENCE, 938, 50-64 [10.1016/j.tcs.2022.10.007].

On k-ary n-cubes and isometric words

Flores M.;
2022-01-01

Abstract

The k-ary n-cubes are a generalization of the hypercubes to alphabets of cardinality k, with k≥2. More precisely, a k-ary n-cube is a graph with kn vertices associated to the k-ary words of length n. Given a k-ary word f, the k-ary n-cube avoiding f is the subgraph obtained deleting those vertices which contain f as a factor. When such a subgraph is isometric to the cube, for any n≥1, the word f is said isometric. A binary word f is isometric if and only if it is Ham-isometric, i.e., for any pair of f-free binary words u and v, u can be transformed in v by complementing the bits on which they differ and generating only f-free words. The case of a k-ary alphabet, with k≥2, is here investigated. From k≥4, the isometricity in terms of cubes is no longer captured by the Ham-isometricity, but by the Lee-isometricity. Then, Ham-isometric and Lee-isometric k-ary words are characterized in terms of their overlaps with errors. The minimal length of two words which witness the non-isometricity of a word f is called its index. The index of f is bounded in terms of its length and the bounds are shown tight by examples.
2022
Anselmo M., Flores M., Madonia M. (2022). On k-ary n-cubes and isometric words. THEORETICAL COMPUTER SCIENCE, 938, 50-64 [10.1016/j.tcs.2022.10.007].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397522005874-main.pdf

Solo gestori archvio

Descrizione: Articolo
Tipologia: Versione Editoriale
Dimensione 498.26 kB
Formato Adobe PDF
498.26 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/618760
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 1
social impact