Optimum mixed level detecting arrays. (English) Zbl 1297.62177

Summary: As a type of search design, a detecting array can be used to generate test suites to identify and detect faults caused by interactions of factors in a component-based system. Recently, the construction and optimality of detecting arrays have been investigated in depth in the case where all the factors are assumed to have the same number of levels. However, for real world applications, it is more desirable to use detecting arrays in which the various factors may have different numbers of levels. This paper gives a general criterion to measure the optimality of a mixed level detecting array in terms of its size. Based on this optimality criterion, the combinatorial characteristics of mixed level detecting arrays of optimum size are investigated. This enables us to construct optimum mixed level detecting arrays with a heuristic optimization algorithm and combinatorial methods. As a result, some existence results for optimum mixed level detecting arrays achieving a lower bound are provided for practical use.


62K15 Factorial statistical designs
94C12 Fault detection; testing in circuits and networks
94A13 Detection theory in information and communication theory
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI arXiv Euclid


[1] Brownlie, J., Plowse, J. and Phadke, M. (1992). Robust Testing of AT&T PMX/StarMail using OATS. ATT Tech. J. 3 41-47.
[2] Cohen, D. M., Dalal, S. R., Parelius, J. and Patton, G. C. (1996). The combinatorial design approach to automatic test generation. IEEE Softw. 13 83-88.
[3] Colbourn, C. J. (2004). Combinatorial aspects of covering arrays. Matematiche ( Catania ) 59 125-172. · Zbl 1195.05017
[4] Colbourn, C. J. and Dinitz, J. H. (2007). The CRC Handbook of Combinatorial Designs . Chapman & Hall/CRC, Boca Raton, FL. · Zbl 1101.05001
[5] Colbourn, C. J. and McClary, D. W. (2008). Locating and detecting arrays for interaction faults. J. Comb. Optim. 15 17-48. · Zbl 1149.90090
[6] Colbourn, C. J., Martirosyan, S. S., Mullen, G. L., Shasha, D., Sherwood, G. B. and Yucas, J. L. (2006). Products of mixed covering arrays of strength two. J. Combin. Des. 14 124-138. · Zbl 1134.05306
[7] Colbourn, C. J., Shi, C., Wang, C. and Yan, J. (2011). Mixed covering arrays of strength three with few factors. J. Statist. Plann. Inference 141 3640-3647. · Zbl 1222.62099
[8] Dalal, S. R., Karunanithi, A. J. N., Leaton, J. M. L., Patton, G. C. P. and Horowitz, B. M. (1999). Model-based testing in practice. In Proceedings of the International Conference on Software Engineering ( ICSE’ 99) 285-294. ACM, New York.
[9] Esmailzadeh, N., Talebi, H., Momihara, K. and Jimbo, M. (2011). A new series of main effects plus one plan for \(2^m\) factorial experiments with \(m=4\lambda\pm 1\) and \(2m\) runs. J. Statist. Plann. Inference 141 1567-1574. · Zbl 1419.62195
[10] Ghosh, S. and Burns, C. (2001). Two general classes of search designs for factor screening experiments with factors at three levels. Metrika 54 1-17. · Zbl 1008.62659
[11] Hedayat, A. S., Sloane, N. J. A. and Stufken, J. (1999). Orthogonal Arrays . Springer, New York. · Zbl 0935.05001
[12] Ji, L. and Yin, J. (2010). Constructions of new orthogonal arrays and covering arrays of strength three. J. Combin. Theory Ser. A 117 236-247. · Zbl 1228.05087
[13] Kuhn, D. R., Wallace, D. R. and Gallo, A. M. (2004). Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng. 30 418-421.
[14] Moura, L., Stardom, J., Stevens, B. and Williams, A. (2003). Covering arrays with mixed alphabet sizes. J. Combin. Des. 11 413-432. · Zbl 1031.05027
[15] Shi, C., Tang, Y. and Yin, J. (2012). The equivalence between optimal detecting arrays and super-simple OAs. Des. Codes Cryptogr. 62 131-142. · Zbl 1283.05045
[16] Shirakura, T., Takahashi, T. and Srivastava, J. N. (1996). Searching probabilities for nonzero effects in search designs for the noisy case. Ann. Statist. 24 2560-2568. · Zbl 0867.62067
[17] Srivastava, J. N. (1975). Designs for searching non-negligible effects. In A Survey of Statistical Design and Linear Models ( Proc. Internat. Sympos. , Colorado State Univ. , Ft. Collins , Colo. , 1973) 507-519. North-Holland, Amsterdam. · Zbl 0313.62060
[18] Tang, Y. and Yin, J. X. (2011). Detecting arrays and their optimality. Acta Math. Sin. ( Engl. Ser. ) 27 2309-2318. · Zbl 1260.05022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.