Conditional expectation algorithms for covering arrays
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\).
- Group construction of covering arrays
- Strength two covering arrays: existence tables and projection
- scientific article; zbMATH DE number 5177325
- Covering arrays and intersecting codes
- t-covering arrays generated by a tiling probability model
- Covering arrays for some equivalence classes of words
- On the state of strength-three covering arrays
- Covering arrays and hash families
- Cover starters for covering arrays of strength two
- Improved strength four covering arrays with three symbols
- Improved strength four covering arrays with three symbols
- Asymptotic and constructive methods for covering perfect hash families and covering arrays
- Algorithmic methods for covering arrays of higher index
- A group-based structure for perfect sequence covering arrays
- Upper bounds on the size of covering arrays
- Cover starters for covering arrays of strength two
This page was built for publication: Conditional expectation algorithms for covering arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2927763)
