Optimal locating arrays for at most two faults

Locating arrays are of interest in generating software test suites to cover all t-way component interactions and locate interaction faults in component-based systems.Recently,Tang,Colbourn and Yin made an investigation into optimal locating arrays in the case where a single fault is to be located.They pointed out that when two or more faults were considered,matters would become rather complicated.To handle those cases generally seems challenging,but is well worth further research.In this paper,we establish a lower bound on the size of locating arrays with at most two faults,and then prove that optimal locating arrays meeting this bound can be equivalently characterized in terms of orthogonal arrays with prescribed properties.Using this characterization,we develop a number of constructions of optimal locating arrays.Two infinite series of optimal locating arrays are then obtained.     

Optimum detecting arrays for independent interaction faults

The use of detecting arrays (DTAs) is motivated by the need to locate and detect interaction faults arising between the factors in a component-based system in software testing. The optimality and construction of DTAs have been investigated in depth for the case in which all the interaction faults are assumed to have the same strength; however, as a practical concern, the strengths of these faults are not always identical. For real world applications, it would be desirable for a DTA to be able to identify and detect faulty interactions of a strength equal to or less than a specified value under the assumption that the faulty interactions are independent from one another. To the best of our knowledge, the optimality and construction of DTAs for independent interaction faults have not been studied systematically before. In this paper, we establish a general lower bound on the size of DTAs for independent interaction faults and explore the combinatorial feature that enable these DTAs to meet the lower bound. Taking advantage of this combinatorial characterization, several classes of optimum DTAs meeting the lower bound are presented.     

Bipartite Locating Array

As a special case of experimental design,locating array is useful for locating interaction faults in component-based systems.In this paper,bipartite locating array is proposed to locate interaction faults between two specific groups.Such arrays are especially suitable for antagonism tests.Based on the definition of bipartite locating array,the lower bound on run sizes are established to measure the optimality for specific parameters.When a single fault is to be located,optimal bipartite locating arrays are proved to be equivalent to certain specific combinatorial configurations.As a result,approaches to constructing optimal bipartite locating arrays are proposed and some infinite classes of optimal bipartite locating arrays are obtained using the corresponding construction met hod.     

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.     

Detecting arrays and their optimality

Detecting arrays were proposed by Colbourn and McClary in 2008, which are of interest in generating software test suites to cover all t-sets of component interactions and detect interaction faults in component-based systems. So far, optimality and constructions of detecting arrays have not been studied systematically. Indeed, no useful benchmark to measure the optimality of detecting arrays has previously been given, and only some sporadic examples of optimal detecting arrays have been found. This paper tries to take the first step by presenting a lower bound on the size of detecting arrays and some methods of constructing optimal detecting arrays. A number of infinite series of optimal detecting arrays are then obtained.     

Covering arrays of higher strength from permutation vectors

A covering array CA(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. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006     

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     

Merging covering arrays and compressing multiple sequence alignments

Covering arrays have been extensively studied, in part because of their applications in testing interacting software components. In this setting, fast and flexible methods are needed to construct covering arrays of close-to-minimum size. However testing scenarios often impose additional structure on the tests that can be selected. We extend a greedy method to construct test suites for complex systems that have a hierarchical structure in which components combine to form subsystems, which in turn form larger subsystems, until the entire system is formed. The algorithm for merging covering arrays that we propose is then shown to have further potential application in the compression of multiple sequence alignments of genomic data.     

Roux-type constructions for covering arrays of strengths three and four

A covering array CA(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. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. Recursive constructions for covering arrays of strengths 3 and 4 are developed, generalizing many “Roux-type” constructions. A numerical comparison with current construction techniques is given through existence tables for covering arrays.      

Variable strength covering arrays

We define and study variable strength covering arrays (also called covering arrays on hypergraphs), which are generalizations of covering arrays and covering arrays on graphs. Variable strength covering arrays have the potential for use in software testing, allowing the engineer to omit the parameter combinations known to not interact in order to reduce the number of tests required. The present paper shows that variable strength covering arrays are relevant combinatorial objects that have deep connections with hypergraph homomorphisms and generalize other important combinatorial designs. We give optimal constructions for special types of hypergraphs, constructions based on columns with uniform occurrence of symbols, and constructions for mixed alphabets.     

Randomized post-optimization of covering arrays

The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful.     

Constructions of covering arrays of strength five

A covering array of size N, strength t, degree k and order v, or a CA(N; t, k, v) in short, is an N × k array on v symbols. In every N × t subarray, each t-tuple occurs in at least one row. Covering arrays have been studied for their significant applications to generating software test suites to cover all t-sets of component interactions. In this paper, we present two constructive methods to obtain covering arrays of strength 5 by using difference covering arrays and holey difference matrices with a prescribed property. As a consequence, some new upper bounds on the covering numbers are derived.     

Covering and radius-covering arrays: Constructions and classification

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.     

A two-stage algorithm for combinatorial testing

Covering arrays are combinatorial structures which have applications in fields like software testing and hardware Trojan detection. In this paper we proposed a two-stage simulated annealing algorithm to construct covering arrays. The proposed algorithm is instanced in this paper through the construction of ternary covering arrays of strength three. We were able to get 579 new upper bounds. In order to show the generality of our proposal, we defined a new benchmark composed of 25 instances of MCAs taken from the literature, all instances were improved.     

On locating all roots of systems of nonlinear equations inside bounded domain using global optimization methods

A novel method of locating all real roots of systems of nonlinear equations is presented here. The root finding problem is transformed to optimization problem, enabling the application of global optimization methods. Among many methods that exist in global optimization literature, Multistart and Minfinder are applied here because of their ability to locate not only the global minimum but also all local minima of the objective function. This procedure enables to locate all the possible roots of the system. Various test cases have been examined in order to validate the proposed procedure. This methodology does not make use of a priori knowledge of the number of the existing roots in the same manner as the corresponding global optimization methodology which does not make use of a priori knowledge of the existed number of local minima. Application of the new methodology resulted in finding all the roots in all test cases. The proposed methodology is general enough to be applied in any root finding problem.     

Combinatorial sums and implicit Riordan arrays

In this paper we present the theory of implicit Riordan arrays, that is, Riordan arrays which require the application of the Lagrange Inversion Formula to be dealt with. We show several examples in which our approach gives explicit results, both in finding closed expressions for sums and, especially, in solving classes of combinatorial sum inversions.     

发现并定位黄球

本文讨论了如何设置红球和蓝球的数量和位置,发现圆柱区域内的黄球并进行定位的问题.我们考虑了一对红球蓝球发现黄球并定位的问题,在此基础上进行扩展,基本解决了黄球的发现并定位的问题.在静止黄球发现问题中,采用了正三角形扩展和正六边形扩展两种方法.在静止黄球的定位问题中,我们结合正三角形和正六边形运用了旋转法和添点法进行扩展.在运动黄球的定位问题中,讨论了体积概率模型和时间概率模型,给出了两种模型的概率求解公式.在系统协同定位模型中,我们给出了发现定位分步模型和周期系统跟踪模型,其中后者在仿真中实现了大于80%的定位性能,该系统可以简单扩展为多目标快速定位问题.此外,文章讨论了精确测量和颜色切换模型,快速定位问题,多目标定位等问题.     

Characterizing phylogenetically decisive taxon coverage

Increasingly, biologists are constructing evolutionary trees on large numbers of overlapping sets of taxa, and then combining them into a ‘supertree’ that classifies all the taxa. In this paper, we ask how much coverage of the total set of taxa is required by these subsets in order to ensure that we have enough information to reconstruct the supertree uniquely. We describe two results — a combinatorial characterization of the covering subsets to ensure that at most one supertree can be constructed from the smaller trees (whichever trees these may be) and a more liberal analysis that asks only that the supertree is highly likely to be uniquely specified by the tree structure on the covering subsets.     

Two‐stage algorithms for covering array construction

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory.     

Generalized orthogonal arrays: Constructions and related graphs

Generalized orthogonal arrays were first defined to provide a combinatorial characterization of (t, m, s)-nets. In this article we describe three new constructions for generalized orthogonal arrays. Two of these constructions are straightforward generalizations of constructions for orthogonal arrays and one employs new techniques. We construct families of generalized orthogonal arrays using orthogonal arrays and provide net parameters obtained from our constructions. In addition, we define a set of graphs associated with a generalized orthogonal array which provide information about the structure of the array. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 31–39, 1999