×

Improved strength four covering arrays with three symbols. (English) Zbl 1386.05017

A covering array \(t\)-CA\((n,k,g)\) is a \(k \times n\) array on \(g\) symbols such that every \(t \times n\) sub-array contains every \(t \times 1\) column on \(g\) symbols at least once. The covering array number \(t\)-CAN\((k,g)\) is the smallest \(n\) for which a \(t\)-CA\((n,k,g)\) exists. Many new upper bounds on \(4\)-CAN\((k,3)\) are here obtained. The record-breaking covering arrays have a large prescribed automorphism group. In particular, projective general linear groups are utilized. Various techniques are further used in attempts to improve the covering arrays found. The authors also study arrays with all parameters \(t\), \(n\), \(k\), and \(g\) fixed. Such structures are in this context called covering arrays with budget constraints. The aim is then to maximize the coverage, which is defined as the number of \(t\)-tuples contained in the column vectors of the array divided by the total number of \(t\)-tuples, which is \(\binom{k}{t}g^t\).

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
05B40 Combinatorial aspects of packing and covering
05B30 Other designs, configurations

Software:

AETG
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akhtar, Y., Maity, S., Chandrasekharan, R.C.: Covering arrays of strength four and software testing. Springer Proc. Math. Stat. 139, 391-398 (2015) · Zbl 1323.05029 · doi:10.1007/978-81-322-2452-5_26
[2] Chateauneuf, M.A., Colbourn, C.J., Kreher, D.L.: Covering arrays of strength three. Designs Codes Cryptogr. 16, 235-242 (1999) · Zbl 0938.05017 · doi:10.1023/A:1008379710317
[3] Chateauneuf, M.A., Kreher, D.L.: On the state of strength-three covering arrays. J. Combin. Design 10(4), 217-238 (2002) · Zbl 1003.05022 · doi:10.1002/jcd.10002
[4] Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: an approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23(7), 437-443 (1997) · doi:10.1109/32.605761
[5] Colbourn, C.J.: Covering array tables for \[t=2,3,4,5,6\] t=2,3,4,5,6. http://www.public.asu.edu/ccolbou/src/tabby/catable.html. Accessed 17 May 2017
[6] Colbourn, C.J.: Conditional expectation algorithms for covering arrays. J. Combin. Math. Combin. Comput. 90, 97-115 (2014) · Zbl 1310.05034
[7] Covering Arrays generated by IPOG-F. http://math.nist.gov/coveringarrays/ipof/ipof-results.html. Accessed 1 May 2017 · Zbl 0938.05017
[8] Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Math. 284, 149-156 (2004) · Zbl 1044.05029 · doi:10.1016/j.disc.2003.11.029
[9] Hartman, A.: Software and Hardware Testing Using Combinatorial Covering Suites. Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, vol. 34, pp. 237-266. Kluwer, Dordrecht (2006) · Zbl 1089.68023 · doi:10.1007/0-387-25036-0_10
[10] Kaner, C., Falk, J., Nguyen, H.Q.: Testing Computer Software, 2nd edn. Wiley, New York (1999) · Zbl 0838.68018
[11] Kuhn, D.R., Wallace, D.R., Gallo, A.M.: Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng. 30(6), 418-421 (2004) · doi:10.1109/TSE.2004.24
[12] Maity, S.: 3-Way software testing with budget constraints. IEICE Trans. Inf. Syst. E-95-D(9), 2227-2231 (2012) · doi:10.1587/transinf.E95.D.2227
[13] Maity, S., Nayak, A.: Improved test generation algorithms for pair-wise testing. In: Proceedings of 16th IEEE international symposium on software reliability engineering, Chicago, pp. 235-244 (2005) · Zbl 1252.05023
[14] Meagher, K., Stevens, B.: Group construction of covering arrays. J. Combin. Designs 13(1), 70-77 (2005) · Zbl 1057.05023 · doi:10.1002/jcd.20035
[15] Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized post-optimization of covering arrays. Eur. J. Combin. 34(1), 91-103 (2013) · Zbl 1252.05023 · doi:10.1016/j.ejc.2012.07.017
[16] Robinson, D.J.S.: A Course in the Theory of Groups, 2nd edn. Springer, New York (1995) · Zbl 0836.20001
[17] Yilmaz, C., Cohen, M., Porter, A.: Covering arrays for efficient fault characterisation in complex configuration spaces. IEEE Trans. Softw. Eng. 32(1), 20-34 (2006) · doi:10.1109/TSE.2006.8
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.