Relevant Constructions Of Covering Arrays

Testing is an important but labor-intensive part that requires a great deal of time and resources during the software and hardware development process. An approach to lowering the cost of software and hardware testing was put forward by Cohen, Dalal, Fredman, and Patton through test suites generated from combinatorial designs. This approach involves identifying parameters that define the space of possible test scenarios, then selecting test scenarios in such a way as to cover all the pairwise interactions between these parameters and their values. This approach corresponds to the concept of covering arrays. A covering array CA (N; t, k, v) is an N x k arrays such that every Nxt sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array.A main problem of covering arrays is to minimize N for given values t, k, v or equivalently to maximize k for given values t, v, N. The case " t=2" has been studied by many authors, see, for instance, Katona, Kleitman and Spencer et al.. The case " t=3" can be found in Chateauneuf, Kreher, Roux, and Sloane et al.. However, very little are known for t-covering arrays with " t≥4". This paper is concerned with t-covering arrays for " t≥4", and its related combinatorial construction.In chapter1; We introduce the background of covering arrays, the definition and known result. Meanwhile, we give some important constructions.In chapter2; We give two new constructions for covering arrays. Firstly, we con-struct CA (N;5, vk, v) using combinatorial techniques and thus obtain new bounds. Sec-ondly, we introduce new structures of CA*and DCA*to construct CA. We use CA*and DCA ’construct CA. A new construction for covering arrays of strength no less than4is developed and the covering array numbers are expected to improve by this construction.In chapter3; We mainly define generalized covering array, and research on its constructions.Tn chapter4; We present the future research problems.