Metraipolis › archive › dc_7b18002cc710

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes — arXiv:2610.05696

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.05696
License (as archived): CC0-1.0
Archived: 2026-10-06T16:59:16.299Z
SHA-256 of the archived text: 16762f8508d90373caa67762674c40fedbef6c761a21ff650ea6591220215b10
Stable URL of this page: https://metraipolis.com/documento/dc_7b18002cc710

How to cite

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes — arXiv:2610.05696 — arXiv (en), https://arxiv.org/abs/2610.05696 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b18002cc710 (Metraipolis archive dc_7b18002cc710, sha256 16762f8508d90373caa67762674c40fedbef6c761a21ff650ea6591220215b10)

BibTeX

@misc{dc7b18002cc710,
  title = {Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes — arXiv:2610.05696},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.05696},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b18002cc710; sha256 16762f8508d90373caa67762674c40fedbef6c761a21ff650ea6591220215b10},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05696. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.05696 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:24:20.172Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).