Constructions of nets via OAs of strength 3 with a prescribed property

The idea of (t, m, s)‐nets was proposed by Niederreiter in 1987. Such nets are highly uniform point distributions in s‐dimensional unit cubes and useful in numerical analysis. It is by now well known that (t, m, s)‐nets can be equivalently described in terms of ordered orthogonal arrays (OOAs). In this article, we describe an equivalence between an OOA and an orthogonal array (OA) with all its derived orthogonal subarrays being resolvable. We then present a number of constructions for OAs where all their derived orthogonal subarrays are resolvable. These results are finally combined to give new series of (t, m, s)‐nets. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:144‐155, 2011     

A simple derivation of the MacWilliams identity for linear ordered codes and orthogonal arrays

In (Can J Math 51(2):326–346, 1999), Martin and Stinson provide a generalized MacWilliams identity for linear ordered orthogonal arrays and linear ordered codes (introduced by Rosenbloom and Tsfasman (Prob Inform Transm 33(1):45–52, 1997) as “codes for the m-metric”) using association schemes. We give an elementary proof of this generalized MacWilliams identity using group characters and use it to derive an explicit formula for the dual type distribution of a linear ordered code or orthogonal array.      

Frequency permutation arrays

Motivated by recent interest in permutation arrays, we introduce and investigate the more general concept of frequency permutation arrays (FPAs). An FPA of length n = mλ and distance d is a set T of multipermutations on a multiset of m symbols, each repeated with frequency λ, such that the Hamming distance between any distinct x,y ∈ T is at least d. Such arrays have potential applications in powerline communication. In this article, we establish basic properties of FPAs, and provide direct constructions for FPAs using a range of combinatorial objects, including polynomials over finite fields, combinatorial designs, and codes. We also provide recursive constructions, and give bounds for the maximum size of such arrays. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 463–478, 2006     

Ideal ramp schemes and augmented orthogonal arrays

Ramp schemes were invented in 1985 by C.R. Blakley and C. Meadows. An $(s,t,n)$-ramp scheme is a generalization of a threshold scheme in which there are two thresholds. Recently, D.R. Stinson established the equivalence of ideal ramp schemes and augmented orthogonal arrays. In this study, some new construction methods for augmented orthogonal arrays are presented and then some new augmented orthogonal arrays are obtained; furthermore, we also provide parameter situations where ideal ramp schemes exist for these obtained augmented orthogonal arrays.     

广义正交表正交性的等价条件

广义正交表是一种类似于正交表的新设计.正交平衡性是广义正交表必须满足的基本要求之一,它是正交表正交性的推广,它能够使得试验因子在方差分析中保持柯赫伦定理成立,因而可以像正交表一样进行试验设计和方差分析,从而不但保证其数据分析模型符合"不自生"逻辑,而且也可以保证试验因子的各种关系比较的数据分析结论具有客观一致性和可重复再现性,但试验次数大幅减少.利用矩阵象技术,提出并证明了广义正交表的组合正交性不但等价于其矩阵象的正交性,而且也等价于其广义关联矩阵的正交性.借助于SAS软件可以方便快速的验证某些区组设计相应的行列设计是否为广义正交表.     

Ideal ramp schemes and related combinatorial objects

In 1996, Jackson and Martin (Jackson and Martin, 1996) proved that a strong ideal ramp scheme is equivalent to an orthogonal array. However, there was no good characterization of ideal ramp schemes that are not strong. Here we show the equivalence of ideal ramp schemes to a new variant of orthogonal arrays that we term augmented orthogonal arrays. We give some constructions for these new kinds of arrays, and, as a consequence, we also provide parameter situations where ideal ramp schemes exist but strong ideal ramp schemes do not exist.     

Construction of Asymmetric Orthogonal Arrays of Strength Three via a Replacement Method

A replacement procedure to construct orthogonal arrays of strength three was proposed by Suen et al. [7]. This method was later extended by Suen and Dey [8]. In this paper, we further explore the replacement procedure to obtain some new families of orthogonal arrays of strength three.     

New constructions for perfect hash families and related structures using combinatorial designs and codes

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and Wei [3]. Using similar methods, we also obtain efficient constructions for separating hash families which result in improved existence results for structures such as separating systems, key distribution patterns, group testing algorithms, cover‐free families and secure frameproof codes. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:189–200, 2000     

On linear programming bounds for nets

It is well known that there are close connections between low-discrepancy point sets and sequences on the one hand, and certain combinatorial and algebraic structures on the other hand. E. g., Niederreiter [1] showed the equivalence between (t, t + 2, s)-nets and orthogonal arrays of strength 2. Some years later this was generalized and made precise in the work of Lawrence [2] as well as Mullen and Schmid [3] by introducing ordered orthogonal arrays. This large class of combinatorial structures yields both new constructions and bounds for the existence of nets and sequences. The linear programming bound for ordered orthogonal arrays was first derived by Martin and Stinson [4]. As in the case of error-correcting codes and orthogonal arrays, it yields a very strong bound for ordered orthogonal arrays, and consequently for nets and sequences. Solving linear programming problems in exact arithmetics is very time-consuming. Using different approaches to reduce the computing time, we have calculated the linear programming bound for a wide parameter range. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

广义正交表和正交表的裂区试验设计法的比较

裂区试验设计方法是在正交表的基础上进行的.根据试验设计的数据分析结论要求具有再现性这一原理,将证明这种裂区试验设计法要有条件的使用才是合理的.由于广义正交表是保证设计表具有再现性的基本设计表,根据广义正交表来研究这种裂区试验设计方法的合理性.研究结果显示在裂区试验设计法对应的设计表是广义正交表,并且相应的数据分析方法采用广义正交表的数据分析方法时,才能保证其数据分析结论具有客观一致性和可重复再现性.     

Products of mixed covering arrays of strength two

A covering array CA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006     

Orthogonal arrays constructed by generalized Kronecker product

In this paper, we propose a new general approach to construct asymmetrical orthogonal arrays, namely generalized Kronecker product. The operation is not usual Kronecker product in the theory of matrices, but it is interesting since the interaction of two columns of asymmetrical orthogonal arrays can be often written out by the generalized Kronecker product. As an application of the method, some new mixed-level orthogonal arrays of run sizes 72 and 96 are constructed.     

Construction of nested orthogonal arrays

A (symmetric) nested orthogonal array is a symmetric orthogonal array OA(N,k,s,g) which contains an OA(M,k,r,g) as a subarray, where M<N and r<s. In this communication, some methods of construction of nested symmetric orthogonal arrays are given. Asymmetric nested orthogonal arrays are defined and a few methods of their construction are described.     

Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

Balanced arrays of strength two and nested (r, λ)-designs

An (r,λ)-design with mutually balanced nested subdesigns (for brevity, (r,λ)-design with MBN) is introduced firstly in this article. It is shown that an r,λ-design with MBN is equivalent to a balanced array of strength 2 with s symbols. By the use of a nested design and an orthogonal array, a construction of an r,λ-design with MBN is given. A direct construction of such an (r,λ)-design, based on the result obtained by Wilson [15], is also given. By these constructions, new balanced arrays with s ≥ 3 are presented. © 1994 John Wiley & Sons, Inc.     

New recursive methods for transversal covers

A transversal cover is a set of gk points in k disjoint groups of size g and a minimum collection of transversal subset s, called blocks, such that any pair of points not contained in the same group appear in at least one block. The case g = 2 was investigated and completely solved by Sperner, Renyi, Katona, Kleitman, and Spencer. For all g, asymptotic results are known, but little is understood for small values of k. Sloane and others have initiated the investigation of g = 3. The present article is concerned with constructive techniques for all g and k. One of the principal constructions generalizes Wilson's theorem for transversal designs. This article also discusses a simulated annealing algorithm for finding transversal covers and gives a table of the best known transversal covers at this time. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 185–203, 1999     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v 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.     

On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002