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

A $t-\text{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'asz 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-\text{a}$ covering array.