Efficient reconstruction of sequences from their subsequences or supersequences
Efficient reconstruction of sequences from their subsequences or supersequences
复制标题
DOI：
10.1006/jcta.2000.3081
复制
发表时间：
2001-02-01
影响因子：
1.1
通讯作者：
Levenshtein, VI
中科院分区：
文献类型：
--
作者：
Levenshtein, VI
本文讨论了字母表F-q={0，1，…，q-1}。对任意非负整数n和t，求出了F-q（n）的两个不同序列的长度为n-t的公共序列集的最大长度N-q（-）（n，t）和长度为n + t的公共超序列集的最大长度N-q（+）（n，t）.数N-q（-）（n，t）+1（分别为N-q（+）（N，t）+1）等于一个未知序列X的长度为n-t的不同序列（长度为n + t的超序列）的最小数目N，该序列X是F-q（n）的一个元素，足以重构它。本文给出了从其长度为n-t的序列的N-q（-）（n，t）+ 1和从其长度为n + r的超序列的N-q（+）（n，t）+ 1恢复X是F-q（n）的元素的简单算法。(C)北京：科学出版社.
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.