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.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.