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

Marcella Anselmo, M.F. (2023). Density of Ham- and Lee- non-isometric k-ary Words. In G. Castiglione, M. Sciortino (a cura di), Proceedings of the 24th Italian Conference on Theoretical Computer Science (pp. 116-128). CEUR-WS.org.

Density of Ham- and Lee- non-isometric k-ary Words

Manuela Flores
;
2023-01-01

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 Klavzar 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.
2023
Marcella Anselmo, M.F. (2023). Density of Ham- and Lee- non-isometric k-ary Words. In G. Castiglione, M. Sciortino (a cura di), Proceedings of the 24th Italian Conference on Theoretical Computer Science (pp. 116-128). CEUR-WS.org.
File in questo prodotto:
File Dimensione Formato  
_ICTCS23_Paper3914.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 414.61 kB
Formato Adobe PDF
414.61 kB Adobe PDF Visualizza/Apri

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/619913
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact