Sequence Covering and Packing Arrays

Combinatorial testing evolved from the statistical design of experiments, and has proven to be an effective and economical method of testing. A combinatorial test suite given by a sequence covering array provides tests so that every occurrence of every t or fewer events is tested with every possible ordering. In this thesis, we investigate sequence covering arrays and related structures known as sequence packing arrays. A sequence covering (packing) array is a set B of N k-sequences on v events, where k ≤ v. In a sequence covering (packing) array every subsequence of t or fewer events, where t ≤ k, appears in at least (most) λ of the sequences in B. The number of tests in a minimum (maximum) size sequence covering (packing) array is called the sequence covering (packing) array number. The goal is usually to minimize (maximize) the size of a sequence covering (packing) array. In the literature, sequence covering (packing) array numbers are only known for small values of k, or for the case when k = v. In this thesis, we determine values of small sequence covering (packing) array numbers for the cases when k < v, λ = 1 and t = 2. We introduce direct and recursive construction strategies. For N ∈ {4, 5, 6, 7, 10, 11}, we determine the set of pairs (v, k) for which the sequence covering number is equal to N. For N ∈ {2, 3, 4, 5}, we also determine the set of pairs for which the sequence packing number is equal to N. Moreover, for each N ∈ {7, 8, 9} we determine sets of pairs (v, k) for which the sequence packing number is at most N. For N ∈ {3, 4, 5, 6, 7, 8, 9}, we were able to improve known bounds on sequence packing array numbers. In most applications, some interactions are infeasible due to system constraints. A set of constraints C is a set of sequences which should not be tested by a test suite given by a sequence covering array. A C-compliant sequence covering array provides tests so that every occurrence of every t or fewer events is tested with every possible ordering, except for the ones given in C. The number of blocks in a minimum size C-compliant sequence covering array is called the C-compliant sequence covering array number. In this thesis, we determine bounds on the number in the case where C is a set of ordered pairs, particularly when the constraint graph induced by C is a subgraph of an oriented multipartite graph. An algorithm to generate constrained sequence covering arrays is also given.