论文标题
完美的序列覆盖阵列
Perfect sequence covering arrays
论文作者
论文摘要
$（n，k）$序列覆盖阵列是$ [n] $的一组排列，因此$ k $的每个序列$ [n] $的不同元素是至少一个排列的子序列。如果有一个正整数$λ$，则$（n，k）$序列覆盖阵列是完美的，使得$ k $的每个序列$ [n] $的不同元素是准确的$λ$的子序列。 尽管已知序列覆盖阵列的最小尺寸的上限和下限相对较近，但对于完美的序列覆盖阵列而言并非如此。在这里，我们为后者提供了新的非平凡界限。特别是，对于$ k = 3 $，我们获得了线性下限和几乎线性上限。
An $(n,k)$ sequence covering array is a set of permutations of $[n]$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of at least one of the permutations. An $(n,k)$ sequence covering array is perfect if there is a positive integer $λ$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of precisely $λ$ of the permutations. While relatively close upper and lower bounds for the minimum size of a sequence covering array are known, this is not the case for perfect sequence covering arrays. Here we present new nontrivial bounds for the latter. In particular, for $k=3$ we obtain a linear lower bound and an almost linear upper bound.
