Efficient reconstruction of sequences from their subsequences or supersequences

In the paper two combinatorial problems for the set F-q(n) of sequences of length,I 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 is an element of F-q(n) which are sufficient for its reconstruction. Simple algorithms to recover X is an element of 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 + r are given. (C) 2001 Academic Press.