Pith. sign in

REVIEW 3 major objections 5 minor 40 references

On the Maximum Size of Codes Under the Damerau-Levenshtein Metric

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every code correcting a constant number $t$ of Damerau-Levenshtein edit types needs redundancy at least $t \log n - O(1)$, matching a known construction up to an additive constant.

desk verdict First upper bounds for Damerau-Levenshtein codes; the deletion/transposition part is solid, but the four-error headline rests on an uncompleted summation. read the letter →

arxiv 2507.04806 v1 pith:VU5K73JM submitted 2025-07-07 cs.IT math.IT

Zuo Ye , Gennian Ge This is my paper · ORCID
classification cs.ITmath.IT MSC 94B6594B6068P30
keywords Damerau-Levenshteinmetricdeletion-correctingcodesadjacenttranspositionasymmetricredundancylowerbounderrorballsfractionalpackingDNAstorage
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes the first upper bounds on the size of error-correcting codes under the Damerau-Levenshtein metric, in which a received word may differ from the sent word by deletions, insertions, substitutions, and adjacent transpositions. The central claim is that for any fixed mix of $t$ such error types, a code of length $n$ over a $q$-ary alphabet contains at most $C q^n / n^t$ codewords for all large $n$, so its redundancy is at least $t \log n - O(1)$. The proof is carried out by computing or bounding the sizes of error balls centered at codewords and then passing through a fractional-packing duality to bound code size. A direct corollary is that a recent binary code correcting one deletion together with asymmetric adjacent transpositions is optimal up to an additive constant. If the bounds are right, the redundancy cost of correcting several independent edit types is simply additive in $\log n$.

What carries the argument

The load-bearing object is the error ball identity $B_{s,t}(x) = T_{\le t}(D_s(x))$, proved as Lemma II.1: every sequence obtained from $x$ by $s$ deletions and at most $t$ adjacent transpositions is obtained by first deleting $s$ symbols and then applying at most $t$ transpositions. This identity converts the two-operation ball into a union of transposition balls over the subsequences in $D_s(x)$. For $s=t=1$, the union is over the $r$ subsequences obtained by deleting one run, and the paper evaluates all pairwise and triple intersections in terms of run-length parameters ($r'_1, r''_1, r^{\mathrm{side}}_1, r^{\mathrm{pair}}_1, r^{\mathrm{in}}_2$), yielding the exact formula. For larger $t$, it substitutes lower bounds on the number of distinct simultaneous transpositions and on the number of subsequences, then uses a fractional-packing (LP dual) argument: assign each received word a weight depending only on its number of runs, chosen so that every error ball has weight at least 1; the total weight of all received words is then an upper bound on code size.

What would settle it

Exhaustively enumerate all $y$ in the ball $B_{s,t}(x)$ for all $x \in \Sigma_q^n$ with small parameters (for instance $q=3$, $n \le 7$, $s=1$, $t=1$). If any measured ball size differs from $r^2 - 4r'_1 - r''_1 - r^{\mathrm{side}}_1 - r^{\mathrm{pair}}_1 - r^{\mathrm{in}}_2$, or any $y$ obtained by $s$ deletions and $t$ transpositions is missing from $T_{\le t}(D_s(x))$, the central claim collapses; otherwise the formula and the bounds stand.

Watch

Extended reading notes

Core claim

The paper's central result is an asymptotic upper bound: for non-negative integers $s_D, s_I, t_T, t_S$ with $t = s_D+s_I+t_T+t_S \geq 1$, every $(s_D, s_I, t_T, t_S)$-correcting code $C \subseteq \Sigma_q^n$ satisfies $|C| \leq C q^n / n^t$ for all sufficiently large $n$, with $C$ depending only on $q$ and the error counts. In redundancy terms, $\log(q^n/|C|) \geq t \log n - O(1)$. The same statement holds with $t$ interpreted as $s+t$ for $s$ deletions and $t$ transpositions, and as $s+t_+ + t_-$ for binary codes correcting $s$ deletions, at most $t_+$ 0-right shifts, and at most $t_-$ 0-left shifts. In the smallest nontrivial case, the 1-deletion-1-transposition ball size is computed exactly as $|B_{1,1}(x)| = r^2 - 4r'_1 - r''_1 - r^{\mathrm{side}}_1 - r^{\mathrm{pair}}_1 - r^{\mathrm{in}}_2$, where $r$ is the number of runs of $x$; this exact count drives the constant in the two-error upper bound. The paper also gives explicit upper bounds for block deletions combined with block transpositions.

Load-bearing premise

The argument assumes Lemma II.1, which says that first deleting and then transposing covers every output reachable by $s$ deletions and at most $t$ transpositions; if this decomposition fails, the exact ball-size formula and the weights built on it would need to be repaired.

Editorial extensions

If this is right

  • Any $q$-ary code correcting one deletion and one adjacent transposition has size at most $O(q^n/n^2)$, hence redundancy at least $2\log n - O(1)$.
  • For constant $s,t$, an $s$-deletion-$t$-transposition code has redundancy at least $(s+t)\log n - O(1)$; the same lower bound applies to block deletions and block transpositions with fixed block length.
  • For codes handling all four Damerau-Levenshtein operations, the redundancy lower bound is $(s_D+s_I+t_T+t_S)\log n - O(1)$.
  • For binary codes correcting $s$ deletions, $t_+$ 0-right shifts and $t_-$ 0-left shifts, the lower bound is $(s+t_+ + t_-)\log n - O(1)$, proving the known construction's redundancy is optimal up to an additive constant.
  • The exact 1-deletion-1-transposition ball-size formula pins down the constant in the two-error upper bound, so the leading term in the maximum code size is known, not just its exponent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the exact $B_{1,1}$ formula can be used directly in a sphere-packing search over small alphabets, potentially locating short codes that meet or approach the $2\log n$ redundancy lower bound.
  • Editorial inference: the run-count weighting scheme suggests explicit near-optimal codes for constant $s,t$ may be built from run-length-constrained ensembles; testing whether the constants $C$ are achievable for $q>2$ is a concrete next step.
  • Editorial inference: since the delete-first order is essential to the upper bound while the transpose-first order fails for $q>2$, non-binary constructions for this metric will likely need to respect that order, a structural constraint the upper bounds make visible.
  • Editorial inference: for the asymmetric binary channel, the theorem implies that distinguishing 0-right from 0-left shifts changes only the constant in the redundancy, not the asymptotic rate.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper derives upper bounds on the size of error-correcting codes under the Damerau–Levenshtein metric, where errors are deletions, insertions, substitutions, and adjacent transpositions. The main technical content is a detailed analysis of deletion–transposition error balls: an exact formula for the 1-deletion-1-transposition ball size (Theorem III.2), lower and upper bounds for general s-deletion-t-transposition balls, and then bounds on code size obtained through the Fazeli–Vardy–Yaakobi hypergraph/LP framework. The paper also gives a block-deletion/block-transposition bound, an extension to all four error types (Theorem VI.1), and a bound for binary codes correcting deletions and asymmetric transpositions (Theorem VII.1). The headline claim is that the redundancy of any code correcting a constant total number t of such errors is at least t log n - O(1), which would imply that Wang et al.'s construction for one deletion plus asymmetric transpositions is optimal up to an additive constant.

Significance. If the results are fully established, the paper would provide the first systematic upper bounds for codes in the Damerau–Levenshtein metric, a setting motivated by DNA storage and peak-shift channels. The strengths of the manuscript are its concrete combinatorial analysis of transposition-ball intersections, the exact ball-size formula in Theorem III.2 (which is verified on an explicit example), and the explicit, parameter-free upper bounds in Theorems IV.1–IV.3. The LP-dual weighting scheme is a principled approach and is carried out in detail in Section IV. The main caveat is that the two theorems supporting the headline claims for the full Damerau–Levenshtein metric and for asymmetric transpositions are not proved to the same standard: their final summation step is delegated to a 'similar argument' without the required estimate. Because the central claim depends on those theorems, the manuscript needs a major revision before the results can be considered established.

major comments (3)
  1. [Section VI, Theorem VI.1] The proof of Theorem VI.1 is incomplete at the load-bearing step. After defining the dual variables w_y, the text says only that the conclusion follows 'from (3) and similar argument in the proof of Theorems IV.1 to IV.3.' What must be shown is that the weighted sum over all y in Sigma_q^{n-sD+sI} is bounded by C q^n / n^t with t = sD+sI+tT+tS. Substituting the number of length-m sequences with r runs, the relevant high-run term has the form (1/n^{sI+tS}) * sum_r q * binom(n', r-1) * (q-1)^{r-1} / ((r-O(1))^{sD} (r-O(1))^{tT}), and bounding this by O(q^{n'}/n^{sD+tT}) requires a concentration estimate for the run count of a random q-ary sequence (for example, E[R^{-a}] = Theta(n^{-a})) or an explicit split of the binomial sum. No such estimate or summation appears in the manuscript. Remark VI.2 explicitly declines to specify n0 or C, so the theorem is not verifiable from the text as written. Since Theorem VI.1 is the basis for the abstract's statement that redundancy is at least t log n - O(1) when all four error types are allowed, this gap must be filled.
  2. [Section VII, Theorem VII.1] The same incompleteness occurs in the proof of Theorem VII.1, which is the theorem used to certify optimality of Wang et al.'s code for asymmetric adjacent transpositions. After the weights w_y are defined, the proof states that the conclusion follows 'from (3) and similar argument in the proof of Theorems IV.1 to IV.3,' but it does not carry out the summation over y in Sigma_q^{n-s}. The binary run-count tail sum has the same structure as in Theorem VI.1, and establishing |C| <= C 2^n / n^{s+t++t-} requires a binomial tail estimate that is not supplied. Because this theorem underpins the paper's main advertised consequence, the proof must be completed explicitly.
  3. [Section V, Theorem V.1] The bound on |C2| in the proof of Theorem V.1 is not proved in the manuscript; it is asserted by saying that 'following similar argument in the proof of [17, Theorem III.2]' one obtains |C2| <= (1.21)^{(s+t+1)b} q^n / n^{s+t+1}. Reference [17] is an unpublished arXiv preprint, and Theorem V.1 is one of the stated contributions of the paper. The argument for |C2| should be reproduced in full, or the theorem should be explicitly stated as conditional on [17]. This is not merely a citation issue: the packing argument for C1 alone does not control the low-run-count part of the code.
minor comments (5)
  1. [Section II-A] In the sentence defining a correcting code, the condition 'B_C(x) ∩ B_C(x')' is missing the required '= empty set'.
  2. [Section IV.B, Theorem IV.2] The statement of Theorem IV.2 says 'single-deletion-single-transposition code' but the theorem is for a single deletion and t transpositions; the title should be corrected.
  3. [Section IV.C, proof of Theorem IV.3] In the displayed estimate for the sum of w_y, the denominator still contains r(y) after the first inequality, whereas the intended bound uses r(x) together with the monotonicity of the run-count expressions; the step r(y) <= r(x)+2t should be written out explicitly.
  4. [Section VI, proof of Lemma VI.1] The lower bound for |B_{0,0,tT,0}(x4)| appears typeset with an exponent on the binomial coefficient that does not follow from Lemma III.7; the expression should be corrected to match the bound ((r-7)/(8tT))^{tT} stated in the lemma.
  5. [Throughout] There are several typographical errors: 'Demerau' for 'Damerau' in Section VI, 'Early Acess' in reference [36], and 'theroem' in Section III.A. These do not affect the mathematics but should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all central bounds are derived from combinatorial ball-size lemmas and an external dual-packing framework; self-citations are auxiliary, not definitional.

full rationale

All load-bearing upper bounds (Theorems IV.1-IV.3, VI.1, and VII.1) are derived through the Fazeli-Vardy-Yaakobi dual-packing framework in Eq. (3), with explicit dual variables w_y chosen from ball-size lower bounds (Theorems III.2-III.4, Lemmas VI.1 and VII.1). The ball-size formulas are proved from first principles via inclusion-exclusion and run-counting; the one imported decomposition, Lemma II.1, is taken from [33, Lemma 4] for the binary case and extended to q>2 with an explicit counterexample. No parameter is fitted to data, and no 'prediction' is defined in terms of the quantity it bounds. The Wang et al. construction enters only as the object whose redundancy is compared with the proved lower bound, not as an input to that bound. Self-citations [17] and [20] are used as prior-work references; [17, Theorem III.2] supplies an auxiliary |C2| estimate inside Theorem V.1, but that is a technical step in a secondary block-error result and does not define or force the paper's central optimal-redundancy conclusion. The manuscript does contain an acknowledged verification gap: the proof of Theorem VI.1 ends with 'Now the conclusion follows from (3) and similar argument in the proof of Theorems IV.1 to IV.3,' and Remark VI.2 says 'the values of n0 and C can be specified. We do not do so here for conciseness.' That is proof incompleteness, not circularity, so it does not raise the circularity score.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities and fits no numerical data. The auxiliary parameters u and epsilon are universal quantifiers used to truncate sums; they are listed for completeness but do not affect the main asymptotic claim. All substantive tools are quoted from prior literature, with proofs given for the new ball-size lemmas.

free parameters (2)
  • u
    Truncation threshold in Theorems IV.1 through IV.3 and V.1; any large enough integer works and it does not change the t log n asymptotic, so it is a proof gadget rather than an empirical fit.
  • epsilon
    Arbitrary slack in (0,1) used to absorb lower-order terms in the same upper bounds; the asymptotic exponent is independent of epsilon.
assumptions (5)
  • standard math Generalized sphere packing bound / LP duality from [37]
    Converts the matching condition into the fractional cover inequality (3), the starting point for Theorems IV.1 through IV.3, VI.1 and VII.1.
  • standard math Deletion ball size bounds |D_s(x)| from [39, eq. (11)] and [40, Theorem 3.4]
    Used in Lemma III.8 and Theorem III.4 lower bounds, and in Lemma VII.1.
  • standard math Insertion and substitution ball size formulas (20) and (21) from [39]
    Used in Lemma VI.1 to handle insertions and substitutions.
  • standard math Binary transposition-deletion commutation [33, Lemma 4]
    Used in Lemma II.1 to show T_{<=t}(D_s(x)) = D_s(T_{<=t}(x)) for q = 2.
  • domain assumption Error counts s, t, t+, t- are constants independent of n
    All upper bounds are asymptotic in n with fixed error multiplicities; the derived C and n0 depend on these constants, and the t log n floor does not apply when errors grow with n.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Maximum Size of Codes Under the Damerau-Levenshtein Metric." pith.science (2026). https://pith.science/paper/VU5K73JM

@misc{pith2026250704806,
  author       = {Pith},
  title        = {Pith review of: On the Maximum Size of Codes Under the Damerau-Levenshtein Metric},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VU5K73JM}},
  note         = {Machine review of arXiv:2507.04806}
}
read the original abstract

The Damerau-Levenshtein distance between two sequences is the minimum number of operations (deletions, insertions, substitutions, and adjacent transpositions) required to convert one sequence into another. Notwithstanding a long history of this metric, research on error-correcting codes under this distance has remained limited. Recently, motivated by applications in DNA-based storage systems, Gabrys \textit{et al} and Wang \texit{et al} reinvigorated interest in this metric. In their works, some codes correcting both deletions and adjacent transpositions were constructed. However, theoretical upper bounds on code sizes under this metric have not yet been established. This paper seeks to establish upper bounds for code sizes in the Damerau-Levenshtein metric. Our results show that the code correcting one deletion and asymmetric adjacent transpositions proposed by Wang \textit{et al} achieves optimal redundancy up to an additive constant.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 31 canonical work pages

  1. [17]

    Codes Correcting Two Bursts of Exactly b deletions,

    Z. Ye, Y . Sun, W. Yu, G. Ge, and O. Elishco, “Codes Correcting Two Bursts of Exactly b deletions,” arXiv, 2024. [Online]. Available: https://arxiv.org/abs/2408.03113

    arXiv 2024

  2. [1]

    A Mathematical Theory of Communication,

    C. E. Shannon, “A Mathematical Theory of Communication,” The Bell System Technical Journal , vol. 27, no. 3, pp. 379–423, Jul. 1948

    work page 1948

  3. [2]

    Bit Loss and Gain Correction Code,

    F. Sellers, “Bit Loss and Gain Correction Code,” IRE Transactions on Information Theory , vol. 8, no. 1, pp. 35–38, Jan. 1962

    work page 1962

  4. [3]

    Binary codes capable of correcting deletions, insertions and reversals,

    V . I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals,” Soviet Physics Doklady , vol. 10, no. 8, pp. 707–710, Feb. 1966

    1966

  5. [4]

    Nonbinary codes, correcting single deletion or insertion (corresp.),

    G. Tenengolts, “Nonbinary codes, correcting single deletion or insertion (corresp.),” IEEE Trans. Inf. Theory , vol. 30, no. 5, pp. 766–769, Sept. 1984

    1984

  6. [5]

    DNA-Based Storage: Trends and Methods,

    S. M. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic, “DNA-Based Storage: Trends and Methods,” IEEE Tran. Mol. Biol. Multi-Scale Commun., vol. 1, no. 3, pp. 230–248, Sept. 2015

    work page 2015

  7. [6]

    A Characterization of the DNA Data Storage Channel,

    R. Heckel, G. Mikutis, and R. N. Grass, “A Characterization of the DNA Data Storage Channel,” Scientific reports, vol. 9, no. 1, pp. 1–12, Jul. 2019

    work page 2019

  8. [7]

    Coding for Racetrack Memories,

    Y . M. Chee, H. M. Kiah, A. Vardy, V . K. Vu, and E. Yaakobi, “Coding for Racetrack Memories,”IEEE Trans. Inf. Theory, vol. 64, no. 11, pp. 7094–7112, Nov. 2018

    work page 2018

Show all 40 references
  1. [8]

    Correcting Multiple Deletions and Insertions in Racetrack Memory,

    J. Sima and J. Bruck, “Correcting Multiple Deletions and Insertions in Racetrack Memory,” IEEE Trans. Inf. Theory , vol. 69, no. 9, pp. 5619–5639, Sept. 2023

    2023

  2. [9]

    Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors,

    K. Cheng, Z. Jin, X. Li, and K. Wu, “Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors,” in Proc. Annu. Symp. Found. Comput. Sci. (FOCS) , Paris, France, Oct. 2018, pp. 200–211

    2018

  3. [10]

    Optimal Document Exchange and New Codes for Insertions and Deletions,

    B. Haeupler, “Optimal Document Exchange and New Codes for Insertions and Deletions,” in Proc. Annu. Symp. Found. Comput. Sci. (FOCS), Baltimore, MD, USA, Nov. 2019, pp. 334–347

    2019

  4. [11]

    Codes Correcting Two Deletions,

    R. Gabrys and F. Sala, “Codes Correcting Two Deletions,” IEEE Trans. Inf. Theory , vol. 65, no. 2, pp. 965–974, Feb. 2019

    2019

  5. [12]

    Two Deletion Correcting Codes From Indicator Vectors,

    J. Sima, N. Raviv, and J. Bruck, “Two Deletion Correcting Codes From Indicator Vectors,” IEEE Trans. Inf. Theory, vol. 66, no. 4, pp. 2375–2391, Apr. 2020

    2020

  6. [13]

    On Optimal k-Deletion Correcting Codes,

    J. Sima and J. Bruck, “On Optimal k-Deletion Correcting Codes,” IEEE Trans. Inf. Theory , vol. 67, no. 6, pp. 3360–3375, Jun. 2021

    2021

  7. [14]

    Explicit two-deletion codes with redundancy matching the existential bound,

    V . Guruswami and J. H ˚astad, “Explicit two-deletion codes with redundancy matching the existential bound,” IEEE Trans. Inf. Theory , vol. 67, no. 10, pp. 6384–6394, Oct. 2021

    2021

  8. [15]

    Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes,

    W. Song and K. Cai, “Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes,” IEEE Trans. Inf. Theory , vol. 69, no. 10, pp. 6470–6484, Oct. 2023

    2023

  9. [16]

    A New Version of q-ary Varshamov-Tenengolts Codes with more Efficient Encoders: The Differential VT Codes and The Differential Shifted VT codes,

    T. T. Nguyen, K. Cai, and P. H. Siegel, “A New Version of q-ary Varshamov-Tenengolts Codes with more Efficient Encoders: The Differential VT Codes and The Differential Shifted VT codes,” IEEE Trans. Inf. Theory , vol. 70, no. 10, pp. 6989–7004, Oct. 2024

    2024

  10. [18]

    Single-Deletion Single-Substitution Correcting Codes,

    I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Single-Deletion Single-Substitution Correcting Codes,” IEEE Trans. Inf. Theory, vol. 69, no. 12, pp. 7659–7671, Dec. 2023

    2023

  11. [19]

    Systematic Codes Correcting Multiple-Deletion and Multiple-Substitution Errors,

    W. Song, N. Polyanskii, K. Cai, and X. He, “Systematic Codes Correcting Multiple-Deletion and Multiple-Substitution Errors,” IEEE Trans. Inf. Theory, vol. 68, no. 10, pp. 6402–6416, Oct. 2022

    2022

  12. [20]

    Binary Codes for Correcting Two Edits,

    Y . Sun and G. Ge, “Binary Codes for Correcting Two Edits,” IEEE Trans. Inf. Theory , vol. 70, no. 10, pp. 6877–6898, Oct. 2024

    2024

  13. [21]

    Two-Insertion/Deletion/Substitution Correcting Codess,

    Y . Pi and Z. Zhang, “Two-Insertion/Deletion/Substitution Correcting Codess,” arXiv, 2024. [Online]. Available: https://doi.org/10.48550/arXiv.2401.11231

    2024 doi arXiv

  14. [22]

    A Technique for Computer Detection and Correction of Spelling Errors,

    F. J. Damerau, “A Technique for Computer Detection and Correction of Spelling Errors,” Commun. ACM, vol. 7, no. 3, pp. 171–176, Mar. 1964

    1964

  15. [23]

    Detecting Substitutions and Transpositions of Characters,

    K. A. S. Abdel-Ghaffar, “Detecting Substitutions and Transpositions of Characters,” The Computer Journal , vol. 41, no. 4, pp. 270–277, Jan. 1998

    1998

  16. [24]

    Peak shift caused by gaussian noise in digital magnetic recording,

    Y . Tahara, Y . Miura, and Y . Ikeda, “Peak shift caused by gaussian noise in digital magnetic recording,” Electron. Commun. Jap. , vol. 59, no. 10, pp. 77–86, 1976

    1976

  17. [25]

    Magnetic and optical storage systems: opportunities for communications technology,

    R. Wood, “Magnetic and optical storage systems: opportunities for communications technology,” in Int. Conf. Commun. , Boston, MA, USA, Jun. 1989, pp. 1605–1612

    1989

  18. [26]

    Shift error correcting modulation codes,

    H. Hilden, D. Howe, and E. Weldon, “Shift error correcting modulation codes,” IEEE Trans. Magn., vol. 27, no. 6, pp. 4600–4605, Nov. 1991

    1991

  19. [27]

    Bounds on the Capacity of the Bit-Shift Magnetic Recording Channel,

    S. Shamai and E. Zehavi, “Bounds on the Capacity of the Bit-Shift Magnetic Recording Channel,” IEEE Trans. Inf. Theory, vol. 37, no. 3, pp. 863–872, May 1991

    1991

  20. [28]

    Error and Erasure Control (d, k) Block Codes,

    H. Ferreira and S. Lin, “Error and Erasure Control (d, k) Block Codes,” IEEE Trans. Inf. Theory , vol. 37, no. 5, pp. 1399–1408, Sept. 1991

    1991

  21. [29]

    A Coding Scheme for Single Peak-Shift Correction in (d, k)-Constrained Channels,

    A. Kuznetsov and A. Vinck, “A Coding Scheme for Single Peak-Shift Correction in (d, k)-Constrained Channels,” IEEE Trans. Inf. Theory , vol. 39, no. 4, pp. 1444–1450, Jul. 1993. 18

    1993

  22. [30]

    Perfect (d, k)-Codes Capable of Correcting Single Peak-Shifts,

    V . Levenshtein and A. Vinck, “Perfect (d, k)-Codes Capable of Correcting Single Peak-Shifts,” IEEE Trans. Inf. Theory , vol. 39, no. 2, pp. 656–662, Mar. 1993

    1993

  23. [31]

    Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis,

    M. Kova ˇcevi´c, “Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis,” IEEE Trans. Inf. Theory, vol. 65, no. 8, pp. 4804–4814, Aug. 2019

    2019

  24. [32]

    Codes Correcting Transpositions of Consecutive Characters,

    M. Kova ˘cevi´c, “Codes Correcting Transpositions of Consecutive Characters,” researchgate, 2024. [Online]. Available: https://www.researchgate.net/ publication/382489864 Codes Correcting Transpositions of Consecutive Characters

    2024

  25. [33]

    Codes in the Damerau Distance for Deletion and Adjacent Transposition Correction,

    R. Gabrys, E. Yaakobi, and O. Milenkovic, “Codes in the Damerau Distance for Deletion and Adjacent Transposition Correction,” IEEE Trans. Inf. Theory, vol. 64, no. 4, pp. 2550–2570, Apr. 2018

    2018

  26. [34]

    Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions,

    L. Schulman and D. Zuckerman, “Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions,” IEEE Trans. Inf. Theory , vol. 45, no. 7, pp. 2552–2557, Nov. 1999

    1999

  27. [35]

    Analysis of asymmetric deterministic bitshift errors in a hard disk file,

    L. Nunnelley, M. Burleson, L. Williams, and I. Beardsley, “Analysis of asymmetric deterministic bitshift errors in a hard disk file,” IEEE Trans. Magn., vol. 26, no. 5, pp. 2306–2308, Sept. 1990

    1990

  28. [36]

    Binary Codes for Correcting Asymmetric Adjacent Transpositions and Deletions,

    S. Wang, V . K. Vu, and V . Y . F. Tan, “Binary Codes for Correcting Asymmetric Adjacent Transpositions and Deletions,” IEEE Trans. Commun. , vol. Early Acess, 2025. [Online]. Available: https://ieeexplore.ieee.org/document/10769481

    2025

  29. [37]

    Generalized Sphere Packing Bound,

    A. Fazeli, A. Vardy, and E. Yaakobi, “Generalized Sphere Packing Bound,” IEEE Trans. Inf. Theory , vol. 61, no. 5, pp. 2313–2334, Mar. 2015

    2015

  30. [38]

    On Levenshtein’s Reconstruction Problem Under Insertions, Deletions, and Substitutions,

    M. Abu-Sini and E. Yaakobi, “On Levenshtein’s Reconstruction Problem Under Insertions, Deletions, and Substitutions,” IEEE Trans. Inf. Theory, vol. 67, no. 11, pp. 7132–7158, Nov. 2021

    2021

  31. [39]

    Efficient Reconstruction of Sequences from Their Subsequences or Supersequences,

    V . I. Levenshtein, “Efficient Reconstruction of Sequences from Their Subsequences or Supersequences,” J. Combinat. Theory, A , vol. 93, no. 2, pp. 310–332, Feb. 2001

    2001

  32. [40]

    Tight Bounds on the Number of String Subsequences,

    D. S. Hirschberg and M. Regnier, “Tight Bounds on the Number of String Subsequences,” J. Discr. Algorithms, vol. 1, no. 1, pp. 123–132, Jun. 2000

    2000

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.