Skip to content
Preprint

Concatenation Locality under Successive Adjacent Transpositions

Nov 2026 · 0 citations · 19 references
Computer Science Mathematics

TL;DR

It is proved that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

Abstract

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

View source

Similar papers

Sep 2026

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardina...

V. Grishin, Aryeh Lev Zabokritskiy · 0 citations
Sep 2026

Polynomially larger deletion codes by linear hashing of substring counts

The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

Eyal En Gad · 4 citations · ⚡1
Sep 2026

Order-Optimal Systematic Permutation Codes for Correcting t Deletions

This paper investigates the construction of full-systematic permutation codes capable of correcting multiple deletions under two complementary models, namely symbol-invariant deletions (SIDs), where surviving symbol values are preserved, and permutation-invariant deletions (PIDs), where the surviving sequence is standa...

Bo Wu, Q. D. Bùi, Kai Niu et al. · 2 citations
Sep 2026

Lower Bounds for all List-Decodable Deletion Codes

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a...

Andrew D. Lin · 0 citations
Preprint Nov 2026

Quadratic reset bounds for finite maximal prefix codes

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theore...

Samrath Singh Chadha · 0 citations
Preprint Nov 2026

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at mo...

Ryan Gabrys, Shubhransh Singhvi, E. Yaakobi · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.