Conditional expectation algorithms for covering arrays (Q2927763)

A covering array \(\mathrm{CA}(N;t,k,v)\) is an \(N\times k\) array satisfying certain conditions, with entries selected from an alphabet of \(v\) symbols. Covering arrays generalize orthogonal arrays: \(t\)-tupes are covered but are not necessarily balanced. An introduction to covering arrays may be found in [\textit{C. J. Colbourn}, Matematiche 59, No. 1--2, 125--172 (2004; Zbl 1195.05017)]. In the present article, the author constructs covering arrays by extending an established conditional expectation algorithm for constructing covering arrays. This new algorithm reduces time and storage requirements by searching only for covering arrays that are invariant under a group action on the set of symbols. (The original algorithm is developed over the course of \textit{R. C. Bryce} and \textit{C. J. Colbourn} [``The density algorithm for pairwise interaction testing'', Software Testing, Verification, and Reliability 17, 159--182 (2007); ``A density-based greedy algorithm for higher strength covering arrays'', ibid. 19, 37--53 (2009)].) Remarkably, while reducing time and storage requirements, this new algorithm also yields, in several cases, best known upper bounds on covering array numbers, i.e., the minimum \(N\) for which a \(\mathrm{CA}(N;t,k,v)\) exists. Best results often occur under Frobenius group actions. This paper focuses on parameters \(4\leq t \leq 6\) and ``small'' values of \(v\).