Search

A known recursive construction for perfect hash families multiplies the number of factors by q, where q is the largest prime power not exceeding the number of symbols. This is generalized to permit multiplication of the number of factors by powers of q; it is also improved upon by restricting the structure of the ingredient designs. For a perfect hash family of strength t, it may be possible to order its rows so that, for each , the first Ni rows form a perfect hash family of strength . This ‘matroshka’ ordering underlies a sometimes substantial reduction in the number of rows generated by the recursive construction. Perfect hash families with useful matroshka orderings are generated using linear orthogonal arrays, and with an effective one-row-at-a-time greedy algorithm.

We construct orthogonal arrays OA λ (k , n) (of strength two) having a row that is repeated m times, where m is as large as possible. In particular, we consider OAs where the ratio m ∕ λ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any k ≥ n + 1 , albeit with large λ. We also study basic OAs; these are optimal OAs in which gcd (m , λ) = 1. We construct a basic OA with n = 2 and k = 4 t + 1 , provided that a Hadamard matrix of order 8 t + 4 exists. This completely solves the problem of constructing basic OAs with n = 2 , modulo the Hadamard matrix conjecture. [ABSTRACT FROM AUTHOR]

Numerous constructions of the best known covering arrays are effective only for specific numbers of symbols. Fusion replaces numerous symbols by one, and can thereby employ such constructions to produce useful covering arrays on fewer symbols. Augmentation instead replaces one symbol by many, permitting the construction of covering arrays from those with fewer symbols. Until this time, augmentation has been of limited value because it introduces substantial redundant coverage. Here a general augmentation method is improved upon by analyzing the classes of interactions to be covered and employing variants of covering arrays, quilting arrays, to reduce the redundancy introduced. For strengths four, five, and six, quilting arrays are produced that can be used in the refined augmentation to produce many best known covering arrays. [ABSTRACT FROM AUTHOR]

Abstract: Covering arrays with mixed alphabet sizes, or mixed covering arrays, are useful generalizations of covering arrays that are motivated by software and network testing. Suppose that there are k factors, and that the ith factor takes values or levels from a set G i of size g i . A run is an assignment of an admissible level to each factor. A mixed covering array, MCA , is a collection of N runs such that for any t distinct factors, , every t-tuple from occurs in factors in at least one of the N runs. When , an MCA is a CA . The mixed covering array number, denoted by MCAN , is the minimum N for which an MCA exists. In this paper, we focus on the constructions of mixed covering arrays of strength three. The numbers MCAN are determined for all cases with and for most cases with . [Copyright &y& Elsevier]

Abstract: A covering array is an array, in which in every subarray, each of the possible t-tuples over symbols occurs at least once. The parameter t is the strength of the array. Covering arrays have a wide range of applications for experimental screening designs, particularly for software interaction testing. A compact representation of certain covering arrays employs “permutation vectors” to encode subarrays of the covering array so that a covering perfect hash family whose entries correspond to permutation vectors yields a covering array. We introduce a method for effective search for covering arrays of this type using tabu search. Using this technique, improved covering arrays of strength 3, 4 and 5 have been found, as well as the first arrays of strength 6 and 7 found by computational search. [Copyright &y& Elsevier]

Abstract: A covering array is an array such that every sub-array contains all t-tuples from symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays. [Copyright &y& Elsevier]

Abstract: A covering array is an array such that every sub-array contains all t-tuples from symbols at least once, where t is the strength of the array. Covering arrays are used in experiments to screen for interactions among t-subsets of k components. Strength two covering arrays have been studied from numerous viewpoints, resulting in a variety of computational, direct, and recursive constructions. Consequently, it can be difficult to determine the smallest covering array that results from known construction. To address this, existence tables for the best currently known covering arrays are presented. In the process, a new direct construction from orthogonal arrays is also introduced. [Copyright &y& Elsevier]