Some New Results on Sequence Reconstruction Problem for Deletion Channels
By: Xiang Wang , Weijun Fang , Han Li and more
Levenshtein first introduced the sequence reconstruction problem in $2001$. In the realm of combinatorics, the sequence reconstruction problem is equivalent to determining the value of $N(n,d,t)$, which represents the maximum size of the intersection of two metric balls of radius $t$, given that the distance between their centers is at least $d$ and the sequence length is $n$. In this paper, We present a lower bound on $N(n,3,t)$ for $n\geq 13$ and $t \geq 4$. For $t=4$, we prove that this lower bound is tight. This settles an open question posed by Pham, Goyal, and Kiah, confirming that $N(n,3,4)=20n-166$ for all $n \geq 13$.
Similar Papers
Sequence Reconstruction over the Deletion Channel
Information Theory
Recovers lost computer code even with missing parts.
Sequence Reconstruction for the Single-Deletion Single-Substitution Channel
Information Theory
Finds shortest codes to fix errors in messages.
Sequence Reconstruction under Channels with Multiple Bursts of Insertions or Deletions
Information Theory
Finds shortest way to send messages without errors.