$t$-Covering Arrays Generated by a Tiling Probability Model

Abstract

A $t-\a$ covering array is an $m\times n$ matrix, with entries from an alphabet of size $\alpha$, such that for any choice of $t$ rows, and any ordered string of $t$ letters of the alphabet, there exists a column such that the "values" of the rows in that column match those of the string of letters. We use the Lovász Local Lemma in conjunction with a new tiling-based probability model to improve the upper bound on the smallest number of columns $N=N(m,t,\alpha )$ of a $t-\a$ covering array.

7 pages