Search

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 $\lambda$ times; this is denoted as $\CA_\lambda(N; t, k, v)$. Covering arrays have applications in the testing of large-scale complex systems; in systems that are nondeterministic, increasing $\lambda$ gives greater confidence in the system's correctness. The \emph{covering array number}, $\CAN_\lambda(t,k,v)$ is the smallest number of rows for which a covering array on the other parameters exists. For general $\lambda$, only several nontrivial bounds are known, the smallest of which was asymptotically $\log k + \lambda \log \log k + o(\lambda)$ 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_\lambda(t,k,v)$ for general $\lambda$ and when $v, t$ are constant using the Stein--Lov\'asz--Johnson paradigm. Second, we improve upon the constants of this method using the Lov\'asz local lemma. Third, when $\lambda=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 $\lambda=1$ of other results. Fourth, we extend this two-stage paradigm further for general $\lambda$ to obtain an even stronger upper bound, including using graph coloring. And finally, we determine a bound on how large $\lambda$ can be for when the number of rows is fixed., Comment: 19 pages

Let $x$ and $y$ be words. We consider the languages whose words $z$ are those for which the numbers of occurrences of $x$ and $y$, as subwords of $z$, are the same (resp., the number of $x$'s is less than the number of $y$'s, resp., is less than or equal). We give a necessary and sufficient condition on $x$ and $y$ for these languages to be regular, and we show how to check this condition efficiently.