Covering arrays with mixed alphabet sizes

Abstract Covering arrays with mixed alphabet sizes, or simply mixed covering arrays , are natural generalizations of covering arrays that are motivated by applications in software and network testing. A (mixed) covering array A of type $\prod _{i=1}^{k}g_i$ is a k × N array with the cells of row i filled with elements from ℤ and having the property that for every two rows i and j and every ordered pair of elements (e,f) ∈ ℤ × ℤ , there exists at least one column c , 1 ≤ c ≤ N , such that A i,c = e and A j,c = f . The (mixed) covering array number, denoted by $ca(\prod _{i=1}^{k}g_i)$ , is the minimum N for which a covering array of type $\prod _{i=1}^{k}g_i$ with N columns exists. In this paper, several constructions for mixed covering arrays are presented, and the mixed covering array numbers are determined for nearly all cases with k = 4 and for a number of cases with k = 5. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 413–432, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10059