Constructions And Existence Of Locating And Detecting Arrays

With the rapid development of computer technology, software system is becomingmore and more enormous. Software testing is a key means to ensure the quality of thesesystems. Interactions among components are complex and numerous. Components areprone to unexpected interaction faults. Ideally we would test all possible interactions,but this is usually infeasible in practice. Combinatorial testing (CT) based on (mixed)covering arrays aims to detect the faults that triggered by interactions among factorsor parameters by designing and executing a small combinatorial test suite to cover therequired combinations of these factorsCombinatorial testing can use a small numberof test cases to test systems efciently while preserving fault detection ability. Thus,testing with a CA or MCA can indicate the presence or absence of interaction faultsup to t factors, i.e., system faults caused by some setting of values to any t factors.However, testing with a CA provides little information to assist in the correction ofinteraction faults. In2008, Colbourn and McClary introduced two special types of(mixed) covering arrays called locating arrrays and detecting arrays. Roughly speak-ing, testing with a (d, t)-locating arrays can locate d interaction faults of strength t;testing with a (d, t)-detecting arrays also can detect whether there are more than dinteraction faults of strength t. At the current time, focusing on building coveringarrays of fewer runs N and higher interaction strength t has become an active areain combinatorial design theory and computer science. This thesis primarily focuseson the constructions and existence of locating and detecting arrays, which involve theoptimaltiy, combinatorial characterization, construction and existence results.There are six chapters in this thesis. The background, some necessary definitionsand related known results are given in the first two chapters.In chapter3, we investigate the constructions and existence of optimal detectingarrays with fixed alphabet sizes. We establish a general lower bound on the sizes of DTAs and explore an equivalence between optimal DTAs and super-simple orthogonalarrays (OAs). Taking advantage of this equivalence, a great number of DTAs areconstructed, which are all optimal in the sense of their sizes. In particular, an optimal(2, t)-DTA(N,5, v) of strength t=2or3is shown to exist whenever v≥3excepting(t, v)∈{(2,6),(3,6)}.In chapter4, we invesitgate optimal locating arrays for at most two faults. Weestablish a lower bound on the sizes of locating arrays, and then prove that optimallocating arrays meeting this bound can be equivalently characterized in terms of or-thogonal arrays with prescribed properties. Using this characterization, we developa number of constructions of optimal locating arrays. Two infinite series of optimallocating arrays are then obtained.In chapter5, super-simple OAs with k=t+2and t∈{2,3,4,5} are investigated.The existence of super-simple OAs with t=3, k=5is given for most case.In chapter6, we investigate the constructions and existence of optimal detectingarrays with mixed alphabet sizes. We establish a general lower bound on the sizes ofDTA with mixed alphabet sizes and explore an equivalence between optimal DTAs andmixed covering arrays (MCAs) with the "d-extendible" property. Taking advantageof this equivalence, a combinatorial figuration is given with k=t+1. The spectrumof this case is determined completely.