Levenshtein’s Reconstruction Problem with Different Error Patterns

In this paper, we consider Levenshtein’s sequence reconstruction problem in which the same codeword is transmitted through N channels each introducing a different set of errors to the transmitted word. In previous works, it has been assumed that each channel provides a unique output word while we assume that each channel introduces a unique set of errors to the transmitted word and hence some output words can be identical. This property seems natural and we also give several results for this problem. Moreover, we also extend optimal decoding algorithm for substitution errors in binary Hamming space to q-ary Hamming spaces. Especially, quaternary Hamming spaces are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas decoding algorithm for simultaneous insertion, deletion and substitution errors in quaternary Hamming spaces.