Hamming–Levenshtein gap of a string
RAIRO - Theoretical Informatics and Applications · 2026 · 60 · 19
DOI: 10.1051/ita/2026020 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Theoretical Informatics and Applications, online erschienen am 04.06.2026. Verfasst von Monther Alfuraidan und 2 weiteren Autor:innen. Die Arbeit nennt 5 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Let u , v be strings over an alphabet Σ with |Σ| ≥ 2. Let L ( u , v ) be the Levenshtein distance and, when | u | = | v |, let H ( u , v ) be the Hamming distance. For equal-length strings, L ( u , v ) ≤ H ( u , v ). For u ∈ Σ*, define hl( u ): = max | v |=| u | (H( u , v )−L( u , v )). Ruth and Lladser [ Discrete Math. 346 (2023) Paper No. 113310] showed that if the run-length of u is at most 2, then hl( u ) = 0; conversely, hl( u ) = 0 implies ρ ( u ) ≤ 2. For p ∈ {2, 3}, we characterize all strings u with hl( u ) = | u | – p . We also identify two types of strings u such that hl( u ) = | u | – 4.
Zitieren
APA
Alfuraidan, M., Algarni, S., & Echi, O. (2026). Hamming–Levenshtein gap of a string. RAIRO - Theoretical Informatics and Applications, 60, 19. https://doi.org/10.1051/ita/2026020
Vancouver
Alfuraidan M, Algarni S, Echi O. Hamming–Levenshtein gap of a string. RAIRO - Theoretical Informatics and Applications. 2026;60:19. doi:10.1051/ita/2026020
BibTeX
@article{Alfuraidan2026,
author = {Alfuraidan, Monther and Algarni, Said and Echi, Othman},
title = {Hamming–Levenshtein gap of a string},
journal = {RAIRO - Theoretical Informatics and Applications},
year = {2026},
volume = {60},
pages = {19},
doi = {10.1051/ita/2026020}
}
EUVIMED