Sequence Reconstruction over the Deletion Channel

In this paper, we consider the Levenshtein’s sequence reconstruction problem in the case where the transmitted codeword is chosen from $\{0,1{\}}^n$ and the channel can delete up to $t$ symbols from the transmitted codeword. We determine the minimum number of channel outputs (assuming that they are distinct) required to reconstruct a list of size $\mathrm{\ell }-1$ of candidate sequences, one of which corresponds to the original transmitted sequence. More specifically, we determine the maximum possible size of the intersection of $\mathrm{\ell }\ge 3$ deletion balls of radius $t$ centered at $x_1,x_2,\dots ,x_{\mathrm{\ell }}$, where $x_i\in \{0,1{\}}^n$ for all $i\in \{1,2,\dots ,\mathrm{\ell }\}$ and $x_i\mathrm{\ne }{x}_j$ for $i\mathrm{\ne }j$, with $n\ge t+\mathrm{\ell }-1$ and $t\ge 1$.