Uncertainty of Reconstructing Multiple Messages from Uniform-Tandem-Duplication Noise

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m> 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from a typical set of strings, consisting a growing fraction of the space size, converging to 1. Thus, we find the trade-off between the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease the required number of reads.