论文标题
覆盖较高索引阵列的上限
Upper Bounds for Covering Arrays of Higher Index
论文作者
论文摘要
a \ emph {覆盖阵列}是$ v $ -ary字母中的$ n \ times k $元素，以至于每个$ n \ times t $ subaray都包含来自$ t $ $ t $的字母的所有$ v^t $ tumplay，至少$λ$ times;这表示为$ \ca_λ（n; t，k，v）$。 覆盖阵列在大规模复杂系统的测试中具有应用；在非确定性的系统中，增加$λ$对系统的正确性有更大的信心。 \ emph {覆盖阵列编号}，$ \can_λ（t，k，v）$是在其他参数上覆盖数组的最小行数。 对于一般$λ$，只有几个非平凡的界限，其中最小的是$ \ log k +λ\ log \ log \ log \ log k + o（λ）$时，$ v，t $是固定的。 另外，已经推测可以删除$ \ log \ log k $项。 首先，我们通过为$ \can_λ（t，k，v）$ vor General $λ$得出渐近的最佳绑定来确认猜想，而当$ v，$ v，t $使用Stein--Lovász-Johnson Paradigm持续不变。 其次，我们使用lovász局部引理来改进该方法的常数。 第三，当$λ= 2 $时，我们扩展了两个阶段的sarkar和colbourn范式，这会改善一般界限，并且通常比$λ=其他结果的$λ= 1 $时产生更好的界限。 第四，我们将这个两阶段的范式进一步扩展到一般$λ$，以获得更强的上限，包括使用图形着色。 最后，我们确定了$λ$在固定行数时的限制。
A \emph{covering array} is an $N \times k$ array of elements from a $v$-ary alphabet such that every $N \times t$ subarray contains all $v^t$ tuples from the alphabet of size $t$ at least $λ$ times; this is denoted as $\CA_λ(N; t, k, v)$. Covering arrays have applications in the testing of large-scale complex systems; in systems that are nondeterministic, increasing $λ$ gives greater confidence in the system's correctness. The \emph{covering array number}, $\CAN_λ(t,k,v)$ is the smallest number of rows for which a covering array on the other parameters exists. For general $λ$, only several nontrivial bounds are known, the smallest of which was asymptotically $\log k + λ\log \log k + o(λ)$ when $v, t$ are fixed. Additionally it has been conjectured that the $\log \log k$ term can be removed. First, we affirm the conjecture by deriving an asymptotically optimal bound for $\CAN_λ(t,k,v)$ for general $λ$ and when $v, t$ are constant using the Stein--Lovász--Johnson paradigm. Second, we improve upon the constants of this method using the Lovász local lemma. Third, when $λ=2$, we extend a two-stage paradigm of Sarkar and Colbourn that improves on the general bound and often produces better bounds than even when $λ=1$ of other results. Fourth, we extend this two-stage paradigm further for general $λ$ to obtain an even stronger upper bound, including using graph coloring. And finally, we determine a bound on how large $λ$ can be for when the number of rows is fixed.
