On k-ary n-cubes and isometric words
- Autori: Anselmo M.; Flores M.; Madonia M.
- Anno di pubblicazione: 2022
- Tipologia: Articolo in rivista
- Parole Chiave: Hamming and Lee distance; Index of a word; k-ary n-cubes; Overlap; Words avoiding factors
- OA Link: http://hdl.handle.net/10447/618760
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.