AUTHORS: Marcella Anselmo Manuela Flores Maria Serafina Madonia

WORK PACKAGE: WP 7 – REVER

URL https://ceur-ws.org/Vol-3587/3914.pdf

Keywords: Isometric words, Overlap with errors, Hamming and Lee distance, Density

Abstract
Isometric k-ary words have been defined referring to the Hamming and the Lee distances. A word is
non-isometric if and only if it has a prefix at distance 2 from the suffix of same length; such a prefix is
called 2-error overlap. The limit density of isometric binary words based on the Hamming distance has
been evaluated by Klavz ˇar and Shpectorov, obtaining that about 8% of all binary words are isometric. In
this paper, the issue is addressed for k-ary words and referring to the Hamming and the Lee distances.
Actually, the only meaningful case of Lee-isometric k-ary words is when k = 4. It is proved that, when the
length of words increases, the limit density of quaternary Ham-isometric words is around 17%, while the
limit density of quaternary Lee-isometric words is even bigger, it is about 30%. The results are obtained
using combinatorial methods and algorithms for counting the number of k-ary isometric words.