KIAM Main page Web Library  •  Publication Search  Русский 

Article, 2001
Journal of Combin. Theory, Ser. A, vol. 93, no. 2, 310-332
Authors: Levenshtein V.I.
Efficient reconstruction of sequences from their subsequences or supersequences
In the paper two combinatorial problems for the set Fqn of sequences of length n over the alphabet Fq={0,1,...,q-1} are considered. The maximum size Nq-(n,t) of the set of common subsequences of length n-t and the maximum size Nq+(n,t) of the set of common supersequences of length n+t of two different sequences of Fqn are found for any nonnegative integers n and t. The number Nq-(n,t)+1 (respectively, Nq+(n,t)+1) is equal to the minimum number N of different subsequences of length n-t (supersequences of length n+t) of an unknown sequence X ∈ Fqn which are sufficient for its reconstruction. Simple algorithms to recover X ∈ Fqn from Nq-(n,t)+1 of its subsequences of length n-t and from Nq+(n,t)+1 of its supersequences of length n+t are given.
sequence, subsequence, supersequence, common subsequence, reconstruction, algorithms.
Publication language: english, pages: 22
Research direction:
Mathematical problems and theory of numerical methods
Source text: