Metraipolis › archive › dc_dcf90d378b46

Coding for Multiple Reverse-Complement and Palindromic Duplications — arXiv:2609.00779

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.00779
License (as archived)
CC0-1.0
Archived
2026-10-17T07:06:47.090Z
SHA-256 of the archived text
fe40c9bd81b4c4b60956e940c335ebe705a509e0370733192211c32e287d04e3
Stable URL of this page
https://metraipolis.com/documento/dc_dcf90d378b46

How to cite

Coding for Multiple Reverse-Complement and Palindromic Duplications — arXiv:2609.00779 — arXiv (en), https://arxiv.org/abs/2609.00779 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dcf90d378b46 (Metraipolis archive dc_dcf90d378b46, sha256 fe40c9bd81b4c4b60956e940c335ebe705a509e0370733192211c32e287d04e3)
BibTeX
@misc{dcdcf90d378b46,
  title = {Coding for Multiple Reverse-Complement and Palindromic Duplications — arXiv:2609.00779},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.00779},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dcf90d378b46; sha256 fe40c9bd81b4c4b60956e940c335ebe705a509e0370733192211c32e287d04e3},
  year = {2026}
}

Archived text

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

Reverse-complement (RC) and palindromic (PAL) duplications copy a length-$k$ block, reverse the copy, and insert it immediately after the original block; an RC duplication also complements the copied symbols. We study $q$-ary codes correcting $t$ such operations performed sequentially, so a later operation may copy symbols created by an earlier one. For fixed $q\geq2$ and $k,t\geq1$, every length-$n$ code $C$ for either channel satisfies $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $1\leq t=t(n)=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For a single RC error over an even alphabet with a fixed-point-free complement, the previously known RC-specific construction applies at odd $k$ and does not cover even $k$. For every even $k$ and any involutive complement, we give a coordinate-wise bijection that turns each RC duplication into a PAL duplication. Applying this bijection to every codeword therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely; encoders and decoders transfer by adding linear-time coordinate passes. For every even $k$, we also determine the maximum number of distinct descendants produced by exactly two errors from one source word. Words alternating between any two distinct alphabet symbols attain this maximum for PAL, and the bijection gives the RC maximizers. For both PAL and RC at fixed even $k$, we prove the existence of two-error-correcting codes with redundancy $4\log_q n+O_{q,k}(1)$. In the binary two-error problem, the converse gives $2\log_2 n-O_k(1)$, leaving a factor-two gap in the best existence bounds.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.00779 — 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-17T06:57:04.902Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).