What does this research mean for the field?

All strings with a Hamming-Levenshtein gap of |u| - 2 or |u| - 3 can be fully characterized, and at least two specific types of strings exist with a gap of |u| - 4. Novelty: ClaimNovelty.INCREMENTAL. Consensus alignment: ConsensusAlignment.NEUTRAL.

What question did this study set out to answer?

The aim is to analyze the Hamming–Levenshtein gap hl(u) for strings based on their properties and run-length.

June 7, 2026

Hamming–Levenshtein gap of a string

Puntos clave

The aim is to analyze the Hamming–Levenshtein gap hl(u) for strings based on their properties and run-length.
Define hl(u) based on maximum values of H(u, v) and L(u, v) for equal-length strings.
Investigate conditions under which hl(u) equals specific values based on string run-length.
Characterize strings with hl(u) equal to |u| - p, for p values of 2 and 3, and identify examples for hl(u) = |u| - 4.
If the run-length of u is at most 2, then hl(u) = 0 (Hamming distance equals Levenshtein distance).
Strings with hl(u) = |u| - 2 or hl(u) = |u| - 3 are fully characterized with respect to their structure.
Two specific string types are identified such that hl(u) = |u| - 4.

Resumen

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.

Preguntar a la IA

Me gusta

Guardar