Efficient reconstruction of sequences from their subsequences or supersequences

Abstract:

In the paper two combinatorial problems for the set F_{q}^{n} of sequences of length n over the alphabet F_{q}={0,1,...,q-1} are considered. The maximum size N_{q}^{-}(n,t) of the set of common subsequences of length n-t and the maximum size N_{q}^{+}(n,t) of the set of common supersequences of length n+t of two different sequences of F_{q}^{n} are found for any nonnegative integers n and t. The number N_{q}^{-}(n,t)+1 (respectively, N_{q}^{+}(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 ∈ F_{q}^{n} which are sufficient for its reconstruction. Simple algorithms to recover X ∈ F_{q}^{n} from N_{q}^{-}(n,t)+1 of its subsequences of length n-t and from N_{q}^{+}(n,t)+1 of its supersequences of length n+t are given.

Keywords:

sequence, subsequence, supersequence, common subsequence, reconstruction, algorithms.

Publication language:english,
pages:22

Research direction:

Mathematical problems and theory of numerical methods