Covering Array Bounds Using Analytical Techniques

Abstract

A $t$-covering array with entries from the alphabet $\mathcal{Q}=\{0,1,\dots ,q-1\}$ is a $k\times n$ stack, so that for any choice of $t$ (typically non-consecutive) columns, each of the $q^t$ possible $t$-letter words over $\mathcal{Q}$ appear at least once among the rows of the selected columns. We will show how a combination of the Lovász local lemma; combinatorial analysis; Stirling's formula; and Calculus enables one to find better asymptotic bounds for the minimum size of $t$-covering arrays, notably for $t=3,4$. Here size is measured in the number of rows, as expressed in terms of the number of columns.

9 pages

References in corpus (1)

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

Cited by in corpus (1)

• Asymptotic size of covering arrays: an application of entropy compression