定位与检测阵列的构作及其存在性
|
摘要
随着计算机技术的飞速发展,软件系统变得越来越庞大,软件测试成为保证这些系统质量的一个关键手段.测试时,组件之间的交互作用复杂、多变,难以预料.理论上,人们可以对所有可能的组件之间的交互作用进行逐一测试,但这在实践上是不可行的.为尽可能少地使用测试用例来有效地检测这些组件以及它们之间的相互作用对系统产生的影响,从而在保证测试用例集错误检测能力的基础上尽可能地降低测试成本,人们提出了基于(混合)覆盖阵((mixed) covering arrays)的软件测试(简称组合测试,combinatorial testing或interaction testing)方法.人们发现以(混合)覆盖阵作为测试方案,可从N次试验结果获知k个组件(因子)中任意t个因子组合是否存在交互影响错误,但具体交互影响的错误模式不能确定.为此,2008年Colbourn和McClary引入了两类新的阵列叫做定位阵列和检测阵列,它们是两类特殊类型的(混合)覆盖阵.粗略地说,用((d,t)-定位阵列作为测试方案,可以根据实验结果确定d个强度为t的交互影响错误；而用((d,t)-检测阵列作为测试方案,同时可以判别是否存在多于d个强度为t的交互影响错误.由此,构作测试用例集个数N尽可能地小且强度t尽可能地高的定位与检测阵列成为当前组合设计理论和计算机科学领域研究的一个热点.本博士论文主要研究定位与检测阵列的构作及其存在性,这中间涉及到定位与检测阵列的最优性判别准则、组合特性刻画、构作以及存在性结果.
本文共有六章.前两章主要给出了本博士论文的研究背景以及相关概念和已知结果.
在第三章,我们主要研究一致水平的最优检测阵列构作及其存在性结果.建立了一致水平的((d,t)-检测阵列的最优性判别准则,证明了最优检测阵列与一类具有超单性质的正交表的等价关系.利用这个等价关系,构造了大量的最优检测阵列.特别地,当v(?)3时,除了可能的例外(t,v)∈{(2,6),(3,6)},最优检测阵列(2,t)-DTA(N,5,v)存在,其中t=2或3.
在第四章,我们研究了至多两个错误的最优定位阵列.首次建立了其存在的最小下界,并且证明了达到下界的最优定位阵列可以用具有预定性质的正交表进行等价描述.利用这个组合特性刻画,我们给出了若干构作最优定位阵列的方法,进而得到了两类新的最优定位阵列.
在第五章,我们研究了k=t+2且t∈{2,3,4,5}超单正交表的构作方法,并给出了t=3,k=5的超单正交表的大部分存在性结果.
在第六章,我们研究了混合水平的最优检测阵列构作及其存在性结果.首次给出了混合水平的检测阵列存在的最小下界,并且描述了达到下界的混合水平的最优检测阵列与一类具有“d-可扩展的”性质的混合覆盖阵的等价关系.利用这个等价描述,给出了k=t+1时的组合构形,同时还完全解决了这种组合构形的存在性.
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.
本文共有六章.前两章主要给出了本博士论文的研究背景以及相关概念和已知结果.
在第三章,我们主要研究一致水平的最优检测阵列构作及其存在性结果.建立了一致水平的((d,t)-检测阵列的最优性判别准则,证明了最优检测阵列与一类具有超单性质的正交表的等价关系.利用这个等价关系,构造了大量的最优检测阵列.特别地,当v(?)3时,除了可能的例外(t,v)∈{(2,6),(3,6)},最优检测阵列(2,t)-DTA(N,5,v)存在,其中t=2或3.
在第四章,我们研究了至多两个错误的最优定位阵列.首次建立了其存在的最小下界,并且证明了达到下界的最优定位阵列可以用具有预定性质的正交表进行等价描述.利用这个组合特性刻画,我们给出了若干构作最优定位阵列的方法,进而得到了两类新的最优定位阵列.
在第五章,我们研究了k=t+2且t∈{2,3,4,5}超单正交表的构作方法,并给出了t=3,k=5的超单正交表的大部分存在性结果.
在第六章,我们研究了混合水平的最优检测阵列构作及其存在性结果.首次给出了混合水平的检测阵列存在的最小下界,并且描述了达到下界的混合水平的最优检测阵列与一类具有“d-可扩展的”性质的混合覆盖阵的等价关系.利用这个等价描述,给出了k=t+1时的组合构形,同时还完全解决了这种组合构形的存在性.
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.
引文
[1] C. J. Colbourn and D. W. McClary, Locating and detecting arrays for interactionfaults, J. Comb. Optim.,2008,15:17-48.
[2] C. J. Colbourn, Combinatorial aspects of covering arrays, Matematiche (Catania),2004,58:121-167.
[3] A. W. Williams and R. L. Probert, A meausre for componeent interaction testcoverage, Proc. ACS/IEEE International Conference on Computer Systems andApplications,2001,301-211.
[4] D. R. Kuhn and M. J. Reilly, An investigation of the applicability of design ofexperiments to software testing, Proc. of the Annual NASA/IEEE Software Engi-neering Workshop (SEW),2002,91-95.
[5] C. R. Rao, Factorial experiments derivable from combinatorial arrangements ofarrays, Suppl. J. Roy. Statist. Soci.,1947,9:128-139.
[6] A. S. Hedayat, N. J. A. Slone and J. Stufken, Orthogonal Arrays, Springer, NewYork,1999.
[7] C. J. Colbourn and J. H. Dinitz, The CRC Handbook of Combinatorial Designs(2nd Edition), CRC Press, Boca Raton, FL,2007.
[8] B. Stevens, Transversal covers and packing, PhD thesis, University of Toronto,1998.
[9] D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, The AETG system:an approach to testing based on combinatorial design, IEEE Trans. Software Eng.,1997,23:437-444.
[10] D. M. Cohen, S. R. Dalal, J. Parelius and G. C. Patton, The combinatorial designapproach to automatic test generation, IEEE Trans. Software Eng.,1996,13:83-88.
[11] M. B. Cohen, Designing test suits for softerware interaction testing, Ph.D. Thesis,University of Auckland,2004.
[12] A. Hartman and L. Raskin, Problems and algorithms for covering arrays, DiscreteMath.,2004,284:149-156.
[13] J. Ko¨rner and M. Lucertini, Compressing inconsistent data, IEEE Trans. Inform.Theory,1994,40:706-715.
[14] N. J. A. Slone, Covering arrays and intersecting codes, J. Combin. Des.,1993,1:51-63.
[15] A. W. Williams, Determination of test configurations for pair-wise interactioncoverage, In Proceedings of the13th International Conference on the Testing ofCommunicating Systems (TestCom2000),59-74.
[16] A. Hartman, Software and Hardware Testing Using Combinatorial Covering Suites,Graph Theory, Combinatorics and Algorithms Operations Research/ComputerScience Interfaces Series,2005,34,237-266.
[17] G. Seroussi and N. H. Bshouty, Vector sets for exhaustive testing of logic circuits,IEEE Trans. Inform. Theory,1988,34,513-522.
[18] B. Stevens and E. Mendelsohn, New recursive methods for transversal covers, J.Combin. Des.,1999,7:185-203.
[19] B. Stevens, L. Moura and E. Mendelsohn, Lower bounds for transversal covers,Des. Codes Cryptogr.,1998,15:(3),279-299.
[20] N. Alon, Explicit constructions of exponential sized families of k-independent sets,Discrete Math.,1986,58:191-193.
[21] S. Poljak, A. Putr and V. Ro¨dl, On qualitatively independent partitions and re-lated problems, Discrete Appl. Math.,1983,6:193-205.
[22] S. Poljak and Z. Tuza, On the maximum number of qualitatively independentpartitions, J. Combin. Theory Ser. A,1989,51:111-1116.
[23] A. R′enyi, Foundation of Probability, Wiley, New York,1971.
[24] D. Kleitman and J. Spencer, Families of k-independent sets, Discrete. Math.,1973,6:266-262.
[25] G. Katona, Two applications(for seach theory and truth function) of Sperner typetheorems, Period. Math. Hungar.,1973,3:19-26.
[26] M. A. Chateauneuf, C. J. Colbourn and D. L. Kreher, Covering arrays of strengththree, Des. Codes Cryptogr.,1999,16:,235-242.
[27] M. B. Cohen, C. J. Colbourn and Alan C. H. Ling, Constructing strength threecovering arrays with augmented annealing, Discrete Math.,2008,308:2709-2722.
[28] M. A. Chateauneuf and D. L. Kreher, On the state of strength-three coveringarrays, J. Combin. Des.,2002,10:217-238.
[29] C.J. Colbourn, S.S. Martirosyan, T. V. Trung and R. A. Walker II, Roux-typeconstructions for covering arrays of strengths three and four, Des. Codes Cryptogr.,2006,41:33-57.
[30] C. J. Colbourn, Strength two covering arrays: Existence tables and projection,Discrete Math.,2008,308:772-786.
[31] L. Ji and J. Yin, Constructions of new orthogonal arrays and covering arrays ofstrength Three, J. Combin. Theory Ser. A,2010,117:236-247.
[32] Y. Li, L. Ji and J. Yin, Covering arrays of strength3and4from holey diferencematrices, Des. Codes Cryptogr.,2009,50:339-350.[33]K. Meagher and B. Stevens, Group construction of covering arrays, J. Combin. Des.,2005,13:70-77.[34]严俊,张健,组合测试：原理与方法,软件学报,2009,20(6),1393-1405.[35]王子元,徐宝文,聂长海,组合测试用例生成技术,计算机科学与探索,2008.2：571-588.[36]C. J. Colbourn, C. Shi, C. Wang and J. Yan, Mixed covering arrays of strength three with few factors, J. Statist. Plann. Inference,2011,141:3640-3647.[37]C. J. Colbourn, S. S. Martirosyan, G. L. Mullen, D. E. Shasha, G. B. Sherwood and J. L. Yucas, Products of mixed covering arrays of strength two, J. Combin. Des.,2006,14:124-138.[38]L. Moura, J. Stardom, B. Stevens and A. Williams, Covering arrays with mixed alphabet sizes, J. Combin. Des.,2003,11:413-432.[39]G. B. Sherwood, Optimal and near-optimal mixed covering arrays by column ex-pansion, Discrete Math.,2008,308:6022-6035.[40]K. Meagher, L. Moura and L. Zekaoui, Mixed covering arrays on graphs, J. Com-bin. Des.,2007,15:393-404.[41]Y. Tang, C. J. Colbourn and J. Yin, Optimality and constructions of locating arrays, J. Stat. Theory Pract,2012,6:20-29.[42]Y. Lei and K. C. Tai, In-Parameter-Order:A test generation strategy for pair-wise testing, Proceeding of the IEEE int'l. Symp. on High Assurance Systems Engineering, Los Alamitos:IEEE Press,1998,254-261.[43]Y. Tang and J. Yin, Detecting arrays and their optimality, Acta Math. Sin.(Engl. Ser.),2011,27:2309-2318.
[44] C. Mart′Inez, L. Moura, D. Panario and B. Stevens, Algorithms to locate errorsusing covering arrays, in Proceedings of the8th Latin American Theoretical Infor-matics Symposium, Lecture Notes in Comput. Sci.4957, E.C. Laber et al., eds.,Springer, New York,2008,504-519.
[45] C. Mart′Inez, L. Moura, D. Panario and B. Stevens, locating errors using ELAs,covering arrays, and adaptive testing algorithms, SIAM J. Discrete Math.,2009,23:1776-1799.
[46] D. Z. Du and F. K. Hwang, Combinatorial group testing and its applications(2ndedn), World Scientific, River Edge,2000.
[47] M. Sobel and P. A. Groll, Group testing to eliminate efciently all defectives in abinomial sample, Bell Syst Tech J,1952,38:1179-1252.
[48] K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics,1952,23:426-434.
[49] H. F. MacNeish, Euler squares, Ann. Math.,1922,23:221-227.
[50] K. A. Bush, A generalization of the dl due to MacNeish, Ann. Math. Stat.,1952,23:293-295.
[51] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press,Cambridge,1999.
[52] D. Jungnickel, On diference matrices, resolvable transversal designs and general-ized Hadamard matrices, Math. Zeitschr,1979,167:49-60.
[53] D. A. Drake, Partial λ-geometries and generalized Hadamard matrices over groups,Can. J. Math.,1979,31:617-627.
[54] J. Yin, Cyclic diference packing and covering arrays, Des. Codes Cryptogr.,2005,37:281-292.
[55] Genian Ge, On (g,4,1)-diference matrices, Discrete Math.,2005,301:164-174.
[56] Y. Chang and L. Ji, Optimal (4up,5,1) optical orthogonal codes, J. Combin. Des.,2004,12:346-361.
[57] Y. Chang and Y. Miao, Constructions for optimal optical orthogonal codes, Dis-crete Math.,2003,261:127-139.
[58] Y. Chang and J. Yin, Further results on optimal optical orthogonal codes withweight4, Discrete Math.,2004,279:135-151.
[59] R. Fuji-Hara, Y. Miao and J. Yin, Optimal (9v,4,1) optical orthogonal codes,SIAM J. Disctere Math.,2001,14:256-266.
[60] G. Ge and J. Yin, Constructions for optimal (v,4,1) optical orthogonal codes,IEEE Trans. Inform. Theory,2001,47:2999-3004.
[61] S. Ma and Y. Chang, A new class of optimal optical orthogonal codes with weightfive, IEEE Trans. Inform. Theory,2004,50:1848-1850.
[62] S. Ma and Y. Chang, Constructions of optimal optical orthogonal codes withweight five, J. Combin. Des.,2005,13:54-69.
[63] Y. Tang and J. Yin, The Combinatorial construction for a Class of Optimal OpticalOrthogonal Codes, Science in China Ser. A,2002,45:1268-1275.
[64] J. Yin, Some combinatorial constructions for optical orthogonal codes, DiscreteMath.,1998,185:201-219.
[65] Y. M. Chee, A.C.H. Ling and Jianxing Yin, Optimal Partitioned Cyclic DiferencePackings for Frequency Hopping and Code Synchronization, IEEE Trans. Inform.Theory,2010,56:5738-5746.
[66] M. J. Colbourn and C. J. Colbourn, Recursive constructions for cyclic block de-signs, J. Statist. Plann. Inference,1984,10:97-103.[67]J. Yin, Constructions of difference covering arrays, J. Combin. Theory Ser. A,2003,104:327-339.[68]E. Seiden, On the problem of construction of orthogonal arrays, Ann. Math. Statist,1954,25:151-156.[69]A. C. Mukhopadhyay, Construction of some series of orthogonal arrays, Sankhya(B),1981,43:81-92.[70]A. S. Hedayat, J. Stufken and Guoqin Su, On difference schemes and orthogonal arrays of strength t, J. Statist. Plann. Inference,1996,56:307-324.[71]H. D. O. F. Gronau and R. C. Mullin, On supersimple2-(υ,κ,λ) designs, J. Combin. Math. Combin. Comput,1992,11:113-121.[72]S. Hartman, On simple and supersimple transversal designs, J. Combin. Des.,2000,8:311-322.[73]A. S. Hedayat, E. Seiden and J. Stufken, On the maximal number of factors and the enumeration of3-symbol orthogonal arrays of strength3and index2, J. Statist. Plann. Inference,1997,58:43-63.[74]J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,1976.[75]郭聃聃,强度(?)3的超单正交表的若干无穷类,苏州大学硕士论文,2011.[76]L. Ji, Y. Li and J. Yin, Constructions of covering arrays of strength five, Des. Codes Cryptogr.,2012,62:199-208.[77]L. Ji and L. Zhu, Consturctions for steiner quadruple systems with a spanning block design, Discrete Math.,2003,261:347-360.[78]M. S. Keranen and D. L. Kreher, Transverse quadruple systems with five holes, J. Combin. Des.,2007,15:315-340.[79]S. Martirosyan and T. V. Trung, On t-covering arrays, Des. Codes Cryptogr.2004,32:323-339.[80]K. J. Nurmela, Upper bounds for covering arrays by tabu search, Discrete. Appl. Math.,2004,138:143-152.[81]沈灏,《组合设计理论》,上海交通大学出版社,2008.[82]D. R. Stinson, Combinatorial Designs:construction and Analysis, Springer, New York,2004.
[2] C. J. Colbourn, Combinatorial aspects of covering arrays, Matematiche (Catania),2004,58:121-167.
[3] A. W. Williams and R. L. Probert, A meausre for componeent interaction testcoverage, Proc. ACS/IEEE International Conference on Computer Systems andApplications,2001,301-211.
[4] D. R. Kuhn and M. J. Reilly, An investigation of the applicability of design ofexperiments to software testing, Proc. of the Annual NASA/IEEE Software Engi-neering Workshop (SEW),2002,91-95.
[5] C. R. Rao, Factorial experiments derivable from combinatorial arrangements ofarrays, Suppl. J. Roy. Statist. Soci.,1947,9:128-139.
[6] A. S. Hedayat, N. J. A. Slone and J. Stufken, Orthogonal Arrays, Springer, NewYork,1999.
[7] C. J. Colbourn and J. H. Dinitz, The CRC Handbook of Combinatorial Designs(2nd Edition), CRC Press, Boca Raton, FL,2007.
[8] B. Stevens, Transversal covers and packing, PhD thesis, University of Toronto,1998.
[9] D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, The AETG system:an approach to testing based on combinatorial design, IEEE Trans. Software Eng.,1997,23:437-444.
[10] D. M. Cohen, S. R. Dalal, J. Parelius and G. C. Patton, The combinatorial designapproach to automatic test generation, IEEE Trans. Software Eng.,1996,13:83-88.
[11] M. B. Cohen, Designing test suits for softerware interaction testing, Ph.D. Thesis,University of Auckland,2004.
[12] A. Hartman and L. Raskin, Problems and algorithms for covering arrays, DiscreteMath.,2004,284:149-156.
[13] J. Ko¨rner and M. Lucertini, Compressing inconsistent data, IEEE Trans. Inform.Theory,1994,40:706-715.
[14] N. J. A. Slone, Covering arrays and intersecting codes, J. Combin. Des.,1993,1:51-63.
[15] A. W. Williams, Determination of test configurations for pair-wise interactioncoverage, In Proceedings of the13th International Conference on the Testing ofCommunicating Systems (TestCom2000),59-74.
[16] A. Hartman, Software and Hardware Testing Using Combinatorial Covering Suites,Graph Theory, Combinatorics and Algorithms Operations Research/ComputerScience Interfaces Series,2005,34,237-266.
[17] G. Seroussi and N. H. Bshouty, Vector sets for exhaustive testing of logic circuits,IEEE Trans. Inform. Theory,1988,34,513-522.
[18] B. Stevens and E. Mendelsohn, New recursive methods for transversal covers, J.Combin. Des.,1999,7:185-203.
[19] B. Stevens, L. Moura and E. Mendelsohn, Lower bounds for transversal covers,Des. Codes Cryptogr.,1998,15:(3),279-299.
[20] N. Alon, Explicit constructions of exponential sized families of k-independent sets,Discrete Math.,1986,58:191-193.
[21] S. Poljak, A. Putr and V. Ro¨dl, On qualitatively independent partitions and re-lated problems, Discrete Appl. Math.,1983,6:193-205.
[22] S. Poljak and Z. Tuza, On the maximum number of qualitatively independentpartitions, J. Combin. Theory Ser. A,1989,51:111-1116.
[23] A. R′enyi, Foundation of Probability, Wiley, New York,1971.
[24] D. Kleitman and J. Spencer, Families of k-independent sets, Discrete. Math.,1973,6:266-262.
[25] G. Katona, Two applications(for seach theory and truth function) of Sperner typetheorems, Period. Math. Hungar.,1973,3:19-26.
[26] M. A. Chateauneuf, C. J. Colbourn and D. L. Kreher, Covering arrays of strengththree, Des. Codes Cryptogr.,1999,16:,235-242.
[27] M. B. Cohen, C. J. Colbourn and Alan C. H. Ling, Constructing strength threecovering arrays with augmented annealing, Discrete Math.,2008,308:2709-2722.
[28] M. A. Chateauneuf and D. L. Kreher, On the state of strength-three coveringarrays, J. Combin. Des.,2002,10:217-238.
[29] C.J. Colbourn, S.S. Martirosyan, T. V. Trung and R. A. Walker II, Roux-typeconstructions for covering arrays of strengths three and four, Des. Codes Cryptogr.,2006,41:33-57.
[30] C. J. Colbourn, Strength two covering arrays: Existence tables and projection,Discrete Math.,2008,308:772-786.
[31] L. Ji and J. Yin, Constructions of new orthogonal arrays and covering arrays ofstrength Three, J. Combin. Theory Ser. A,2010,117:236-247.
[32] Y. Li, L. Ji and J. Yin, Covering arrays of strength3and4from holey diferencematrices, Des. Codes Cryptogr.,2009,50:339-350.[33]K. Meagher and B. Stevens, Group construction of covering arrays, J. Combin. Des.,2005,13:70-77.[34]严俊,张健,组合测试：原理与方法,软件学报,2009,20(6),1393-1405.[35]王子元,徐宝文,聂长海,组合测试用例生成技术,计算机科学与探索,2008.2：571-588.[36]C. J. Colbourn, C. Shi, C. Wang and J. Yan, Mixed covering arrays of strength three with few factors, J. Statist. Plann. Inference,2011,141:3640-3647.[37]C. J. Colbourn, S. S. Martirosyan, G. L. Mullen, D. E. Shasha, G. B. Sherwood and J. L. Yucas, Products of mixed covering arrays of strength two, J. Combin. Des.,2006,14:124-138.[38]L. Moura, J. Stardom, B. Stevens and A. Williams, Covering arrays with mixed alphabet sizes, J. Combin. Des.,2003,11:413-432.[39]G. B. Sherwood, Optimal and near-optimal mixed covering arrays by column ex-pansion, Discrete Math.,2008,308:6022-6035.[40]K. Meagher, L. Moura and L. Zekaoui, Mixed covering arrays on graphs, J. Com-bin. Des.,2007,15:393-404.[41]Y. Tang, C. J. Colbourn and J. Yin, Optimality and constructions of locating arrays, J. Stat. Theory Pract,2012,6:20-29.[42]Y. Lei and K. C. Tai, In-Parameter-Order:A test generation strategy for pair-wise testing, Proceeding of the IEEE int'l. Symp. on High Assurance Systems Engineering, Los Alamitos:IEEE Press,1998,254-261.[43]Y. Tang and J. Yin, Detecting arrays and their optimality, Acta Math. Sin.(Engl. Ser.),2011,27:2309-2318.
[44] C. Mart′Inez, L. Moura, D. Panario and B. Stevens, Algorithms to locate errorsusing covering arrays, in Proceedings of the8th Latin American Theoretical Infor-matics Symposium, Lecture Notes in Comput. Sci.4957, E.C. Laber et al., eds.,Springer, New York,2008,504-519.
[45] C. Mart′Inez, L. Moura, D. Panario and B. Stevens, locating errors using ELAs,covering arrays, and adaptive testing algorithms, SIAM J. Discrete Math.,2009,23:1776-1799.
[46] D. Z. Du and F. K. Hwang, Combinatorial group testing and its applications(2ndedn), World Scientific, River Edge,2000.
[47] M. Sobel and P. A. Groll, Group testing to eliminate efciently all defectives in abinomial sample, Bell Syst Tech J,1952,38:1179-1252.
[48] K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics,1952,23:426-434.
[49] H. F. MacNeish, Euler squares, Ann. Math.,1922,23:221-227.
[50] K. A. Bush, A generalization of the dl due to MacNeish, Ann. Math. Stat.,1952,23:293-295.
[51] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press,Cambridge,1999.
[52] D. Jungnickel, On diference matrices, resolvable transversal designs and general-ized Hadamard matrices, Math. Zeitschr,1979,167:49-60.
[53] D. A. Drake, Partial λ-geometries and generalized Hadamard matrices over groups,Can. J. Math.,1979,31:617-627.
[54] J. Yin, Cyclic diference packing and covering arrays, Des. Codes Cryptogr.,2005,37:281-292.
[55] Genian Ge, On (g,4,1)-diference matrices, Discrete Math.,2005,301:164-174.
[56] Y. Chang and L. Ji, Optimal (4up,5,1) optical orthogonal codes, J. Combin. Des.,2004,12:346-361.
[57] Y. Chang and Y. Miao, Constructions for optimal optical orthogonal codes, Dis-crete Math.,2003,261:127-139.
[58] Y. Chang and J. Yin, Further results on optimal optical orthogonal codes withweight4, Discrete Math.,2004,279:135-151.
[59] R. Fuji-Hara, Y. Miao and J. Yin, Optimal (9v,4,1) optical orthogonal codes,SIAM J. Disctere Math.,2001,14:256-266.
[60] G. Ge and J. Yin, Constructions for optimal (v,4,1) optical orthogonal codes,IEEE Trans. Inform. Theory,2001,47:2999-3004.
[61] S. Ma and Y. Chang, A new class of optimal optical orthogonal codes with weightfive, IEEE Trans. Inform. Theory,2004,50:1848-1850.
[62] S. Ma and Y. Chang, Constructions of optimal optical orthogonal codes withweight five, J. Combin. Des.,2005,13:54-69.
[63] Y. Tang and J. Yin, The Combinatorial construction for a Class of Optimal OpticalOrthogonal Codes, Science in China Ser. A,2002,45:1268-1275.
[64] J. Yin, Some combinatorial constructions for optical orthogonal codes, DiscreteMath.,1998,185:201-219.
[65] Y. M. Chee, A.C.H. Ling and Jianxing Yin, Optimal Partitioned Cyclic DiferencePackings for Frequency Hopping and Code Synchronization, IEEE Trans. Inform.Theory,2010,56:5738-5746.
[66] M. J. Colbourn and C. J. Colbourn, Recursive constructions for cyclic block de-signs, J. Statist. Plann. Inference,1984,10:97-103.[67]J. Yin, Constructions of difference covering arrays, J. Combin. Theory Ser. A,2003,104:327-339.[68]E. Seiden, On the problem of construction of orthogonal arrays, Ann. Math. Statist,1954,25:151-156.[69]A. C. Mukhopadhyay, Construction of some series of orthogonal arrays, Sankhya(B),1981,43:81-92.[70]A. S. Hedayat, J. Stufken and Guoqin Su, On difference schemes and orthogonal arrays of strength t, J. Statist. Plann. Inference,1996,56:307-324.[71]H. D. O. F. Gronau and R. C. Mullin, On supersimple2-(υ,κ,λ) designs, J. Combin. Math. Combin. Comput,1992,11:113-121.[72]S. Hartman, On simple and supersimple transversal designs, J. Combin. Des.,2000,8:311-322.[73]A. S. Hedayat, E. Seiden and J. Stufken, On the maximal number of factors and the enumeration of3-symbol orthogonal arrays of strength3and index2, J. Statist. Plann. Inference,1997,58:43-63.[74]J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,1976.[75]郭聃聃,强度(?)3的超单正交表的若干无穷类,苏州大学硕士论文,2011.[76]L. Ji, Y. Li and J. Yin, Constructions of covering arrays of strength five, Des. Codes Cryptogr.,2012,62:199-208.[77]L. Ji and L. Zhu, Consturctions for steiner quadruple systems with a spanning block design, Discrete Math.,2003,261:347-360.[78]M. S. Keranen and D. L. Kreher, Transverse quadruple systems with five holes, J. Combin. Des.,2007,15:315-340.[79]S. Martirosyan and T. V. Trung, On t-covering arrays, Des. Codes Cryptogr.2004,32:323-339.[80]K. J. Nurmela, Upper bounds for covering arrays by tabu search, Discrete. Appl. Math.,2004,138:143-152.[81]沈灏,《组合设计理论》,上海交通大学出版社,2008.[82]D. R. Stinson, Combinatorial Designs:construction and Analysis, Springer, New York,2004.