CS Paper Radar

Synchronization Strings over the Optimal Alphabet

Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao

cs.IT cs.DMcs.FL ·submitted 2026-09-03 17:24 UTC · v2
theory

Abstract

Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subsequent work proved that four symbols suffice for some fixed parameter epsilon < 1, whereas two symbols cannot support arbitrarily long synchronization strings. We resolve the remaining ternary case: every length admits a ternary 2001/2002-synchronization string. Thus three is the exact minimum constant alphabet size. A computer-assisted refinement based on a larger 54-uniform family yields ternary epsilon-synchronization strings for every epsilon > 215/216. The previous four-symbol construction uses a ternary square-free backbone to exclude short repetitions and a fourth symbol to carry long-range synchronization marks. Our main technical contribution is a local-entropy transfer theorem: every square-free block-local source with a positive interval conditional min-entropy rate supports synchronization strings with a fixed gap. We instantiate this theorem using occurrence-wise branching in a Brinkhuis family. Every outcome remains ternary and square-free, while every long interval retains linear conditional min-entropy after all choices outside it are exposed. A deletion-ball estimate converts this entropy into an exponentially small probability of a near-complete common subsequence between adjacent intervals, and an asymmetric Lovasz Local Lemma enforces all interval constraints simultaneously. The same framework also yields exponentially many valid words, synchronization circles, and synchronization within a class of extremal square-free words. Adding constraints on distant intervals gives a Las Vegas construction in expected O(n^2 log^3(n+2)) time.

Comment
46 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On smallest synchronizing terms over constant alphabets

cs.FL ·2026-09-01 ·Luisa Herrmann, Richard Mörbitz
theory similarity 0.64
Abstract

We show a subexponential lower bound on the reset threshold of synchronizing deterministic finite tree automata (DTA) over alphabets of just two symbols. This significantly improves the previous one, which was quadratic in the number of states. Our result also narrows the gap towards the lower bound for DTA over alphabets that grow linearly with the number of states, as well as the best known upper bound, both of which are currently exponential.

0.08

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

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.61
Abstract · 52 pages

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 cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

0.12

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.60
Abstract · 32 pages

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$.

0.28

Repetition Avoidance in Curling-Number Transforms

cs.DM math.COcs.FL ·2026-08-16 ·Geoffrey Caveney, Haoxuan, Dong, Jeffrey Shallit
similarity 0.56
Abstract

We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based morphic constructions and exhaustive finite searches. A ternary word for which both ${\bf w}$ and $C({\bf w})$ are overlap-free has length at most $84$, whereas over four letters an infinite example exists. Hence $4$ is the smallest alphabet size admitting simultaneous infinite overlap-freeness. The infinite constructions are verified in Walnut; the finite maxima are obtained by exhaustive breadth-first search and checked independently.

0.04

Order-Optimal Systematic Permutation Codes for Correcting t Deletions

cs.IT ·2026-09-29 ·Bolin Wu, Quan D. Bui, Kai Niu, Van Khu Vu, Shuche Wang
similarity 0.56
Abstract

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 standardized to a permutation. For any fixed integer $t \ge 1$ and all sufficiently large message lengths $n$, our proposed encoders map any message permutation of length $n$ to a codeword by inserting distinct redundancy symbols while strictly preserving the sequence order of the original message symbols. The proposed constructions correct up to $t$ deletions using $7t-1$ redundancy markers for PIDs and $4t$ redundancy markers for SIDs, achieving redundancies of $(7t-1)\log n + O_t(1)$ bits and $4t\log n + O_t(1)$ bits, respectively. Both code families are uniformly constructible, encodable, and decodable in $n^{O(t)}$ time. The underlying framework stores an inner deletion-correcting syndrome in the relative positions of redundancy markers via an algebraic outer code based on integer moments and residual graph coloring. We further extend this framework to fixed-composition and strictly $λ$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $λ> t$.

0.39

Block-exchange descent for insertion: commuting projections and minimum masks

cs.FL math.CO ·2026-10-29 ·Haobo Ma, Wenlin Zhang, Charles E. Hughes
theorycode/data similarity 0.55
Abstract · 22 pages, 10 tables. Software and verification data: https://github.com/the-omega-institute/insertion-degree-descent/releases/tag/v1.0

For fixed nonempty words $u,v$, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations. We prove that, after a block exchange from a minimum mask of degree $r$, the minimum over masks with commuting source projections is exactly $r-1$; a larger decrease occurs precisely when a noncommuting mask has fewer runs. If either source is unary, every such exchange is exact. We prove an explicit repair for an infinite periodic degree-three family. Computer-assisted results establish first-mask descent through combined length seventeen over every alphabet, degree-three first-mask descent through length thirty, and a uniform repair of all degree-three failures through length thirty, including all further letter identifications. Counterexamples to arbitrary, first, and last minimum-mask choices explain the need for alternative masks. Finally, we prove that minimum iteration depths have no gaps for arbitrary languages. General block-exchange descent and Singleton No-Gap remain open.

0.50

Copying Under Repetition: From Prefix Matching to Position Hashing

cs.LG cs.CL ·2026-10-19 ·Anxin Guo, Tianlong Huang, Chenxiao Yang, Zhiyuan Li
theory similarity 0.54
Abstract

Frontier LLMs can copy random text almost flawlessly, yet they often overrun or truncate long blocks of repeated characters. In repeated strings, matching local content no longer reliably identifies where copying should continue or when it should stop. Nevertheless, we show that a two-layer transformer with $O(\log\log N)$-bit precision and $O(\log N/\log\log N)$ width can copy every string up to a chosen design horizon $N$ and terminate correctly under arbitrary repetition. We use RoPE-style rotations of attention values and outputs (VO-rotations) with small prime periods to encode distances from delimiter anchors modulo those primes. By the Chinese Remainder Theorem, these periodic encodings jointly distinguish all required distances, allowing one retrieval rule to select either the next source token or the end marker. In contrast, we prove a width-independent impossibility result for copying under sequential finite-precision softmax accumulation. It applies to transformers whose only positional input is an additive attention bias that eventually becomes constant, including NoPE and a recursive implementation of ALiBi. Once an identical-token run exceeds the resulting saturation threshold, further repetitions leave the logits unchanged. If this threshold grows sublinearly with $N$, these models cannot both complete a long all-identical copy and stop correctly, a pattern resembling the termination errors of frontier LLMs. In synthetic copying experiments, baseline transformer models fail on long repeated strings even within the training range. Trained VO models, by contrast, generalize beyond the training lengths with near-perfect accuracy up to length $\approx5005$, the selected primes' period product.

0.14

Undecidability of Confluence for Binary Length-Reducing Cycle Rewriting

cs.LO cs.FL ·2026-08-19 ·Graham Campbell
similarity 0.54
Abstract

Confluence guarantees that diverging rewrite choices can always be rejoined. For finite terminating string- and term-rewriting systems, confluence is decidable by critical-pair analysis, and in polynomial time for length-reducing strings. For finite terminating (hyper)graph transformation systems, in contrast, confluence is undecidable. We show that undecidability already appears for words on a circle, that is, strings up to rotation. Confluence of finite cycle-rewriting systems over the fixed alphabet $\{0,1\}$ is undecidable, indeed $Π^0_1$-complete, even when every rule has a nonempty right-hand side and strictly reduces length. Under this restriction termination is syntactically evident, and derivations from a nonempty length-$n$ cycle have fewer than $n$ steps. The same holds over every fixed alphabet with at least two letters, while the one-letter case is decidable. Rotation alone separates cyclic from string rewriting. The proof compiles a deterministic verifier into a weighted cycle system with one controlled branch, then into a binary length-reducing system via a run-length code whose cleanup rules send every reducible malformed cycle to one error normal form.

0.29