11:45 am, Seminar Hall
Covering arrays and Generalizations
Covering arrays have been successfully applied in the design of test suites for testing systems such as software, circuits and networks, where failures can be caused by the interaction between their parameters A covering array t-CA(n, k, g), of size n, strength t, degree k, and order g, is a k Ã n array on g symbols such that every t Ã n sub-array contains every t Ã 1 column on g symbols at least once. It is desirable in most applications to minimize the size n. In this talk, we consider a generalization of covering arrays called mixed covering arrays on hypergraphs. We introduce five basic hypergraph operations to construct optimal mixed covering arrays on 2-tree hypergraphs, α-acyclic 3-uniform hypergraphs, a family of conformal 3-uniform hypertrees, and on some specific 3-uniform cycle hypergraphs. We also discuss some results based on an algebraic construction that improves many of the best known upper bounds on n for covering arrays 4-CA(n, k, g) with g = 3 and constructs several strength three and strength four testing arrays with high coverage.