×

zbMATH — the first resource for mathematics

Algebraic modelling of covering arrays. (English) Zbl 1383.05048
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 149-170 (2017).
Summary: We introduce a novel technique to model and compute binary covering arrays, discrete combinatorial structures, based on a tuple-level modelling and using methods arising from linear algebra, commutative algebra and symbolic computation. Concrete instances of covering arrays for given parameters will arise as points in a generated variety of a system of multivariate polynomial equations with Gröbner bases playing an important role.
For the entire collection see [Zbl 1379.13001].

MSC:
05B40 Combinatorial aspects of packing and covering
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
AETG; Magma
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Avila-George, H., Torres-Jimenez, J., Hernández, V.: New bounds for ternary covering arrays using a parallel simulated annealing. Math. Probl. Eng. (2012)
[2] 2. Becker, T., Weispfenning, V.: Gröbner bases. In: A Computational Approach to Commutative Algebra. Graduate Studies in Mathematics, vol. 141. Springer, New York (1993) · Zbl 0772.13010
[3] 3. Borges-Quintana, M., Borges-Trenard, M.A., Fitzpatrick, P., Martínez-Moro, E.: Gröbner bases and combinatorics for binary codes. Appl. Algebra Eng. Commun. Comput. 19 (5), 393-411 (2008) · Zbl 1192.94130
[4] 4. Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symb. Comput. 24 (3-4), 235-265 (1997). Computational algebra and number theory (London, 1993) · Zbl 0898.68039
[5] 5. Bracho-Rios, J., Torres-Jimenez, J., Rodriguez-Tello, E.: A new backtracking algorithm for constructing binary covering arrays of variable strength. In: MICAI 2009: Advances in Artificial Intelligence, pp. 397-407. Springer, New York (2009)
[6] 6. Bryce, R.C., Colbourn, C.J.: The density algorithm for pairwise interaction testing. Softw. Test. Verif. Reliab. 17 (3), 159-182 (2007)
[7] 7. Buchberger, B.: Bruno Buchberger’s phd thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41 , 475-511 (2006). doi: · Zbl 1158.01307
[8] 8. 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-444 (1997)
[9] 9. Colbourn, C.: Table for CAN(2,k,2) for k up to 20000.
[10] 10. Colbourn, C.J.: Combinatorial aspects of covering arrays. Le Mathematiche LIX (I-II), pp. 125-172 (2004) · Zbl 1195.05017
[11] 11. Colbourn, C.J.: Covering arrays from cyclotomy. Des. Codes Cryptogr. 55 (2-3), 201-219 (2010) · Zbl 1215.05019
[12] 12. Colbourn, C.J., Dinitz, J.H.: Handbook of Combinatorial Designs. CRC Press, Boca Raton (2006) · Zbl 0836.00010
[13] 13. Faugere, J.C.: A new efficient algorithm for computing Gröbner bases (f 4). J. Pure Appl. Algebr. 139 (1), 61-88 (1999) · Zbl 0930.68174
[14] 14. Faugère, J.C.: A new efficient algorithm for computing grÖbner bases without reduction to zero (f5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC ’02), pp. 75-83. ACM, New York (2002). doi:
[15] 15. Gonzalez-Hernandez, L., Rangel-Valdez, N., Torres-Jimenez, J.: Construction of mixed covering arrays of strengths 2 through 6 using a tabu search approach. Discret. Math. Algorithm Appl. 4 (03), 1250,033 (2012) · Zbl 1315.68108
[16] 16. Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discret. Math. 284 (1), 149-156 (2004) · Zbl 1044.05029
[17] 17. Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test problem. Constraints 11 (2-3), 199-219 (2006) · Zbl 1103.68810
[18] 18. IPOG-F: CA(2,10,2).
[19] 19. IPOG-F: CA(2,16,2).
[20] 20. IPOG-F: CA(2,17,2).
[21] 21. IPOG-F: CA(2,9,2).
[22] 22. ITL, N.: Covering array tables.
[23] 23. Kleitman, D.J., Spencer, J.: Families of k-independent sets. Discret. Math. 6 (3), 255-262 (1973) · Zbl 0269.05002
[24] 24. Kotsireas, I., Koukouvinos, C., Seberry, J.: Hadamard ideals and hadamard matrices with circulant core. J. Combin. Math. Combin. Comput. 57 , 47-63 (2006) · Zbl 1117.05017
[25] 25. Kotsireas, I., Koukouvinos, C., Seberry, J.: Hadamard ideals and Hadamard matrices with two circulant cores. Eur. J. Comb. 27 (5), 658-668 (2006) · Zbl 1087.05012
[26] 26. Kotsireas, I.S., Kutsia, T., Simos, D.E.: Constructing orthogonal designs in powers of two: Gröbner bases meet equational unification. In: 26th International Conference on Rewriting Techniques and Applications (RTA), June 29 to July 1, 2015, Warsaw, pp. 241-256 (2015) · Zbl 1366.68122
[27] 27. Koukouvinos, C., Simos, D.E., Zafeirakopoulos, Z.: An algebraic framework for extending orthogonal designs. In: ISSAC ’11: Abstracts of Poster Presentations of the 36th International Symposium on Symbolic and Algebraic Computation, ACM Communications in Computer Algebra, vol. 45, pp. 123-124 (2011) · Zbl 1305.68361
[28] 28. Koukouvinos, C., Simos, D.E., Zafeirakopoulos, Z.: A Gröbner bases method for complementary sequences. In: Proceedings of Applications of Computer Algebra (ACA), p. 255. Málaga (2013)
[29] 29. Kuhn, R., Kacker, R., Lei, Y., Hunter, J.: Combinatorial software testing. Computer 8 , 94-96 (2009)
[30] 30. Kuhn, D.R., Kacker, R.N., Lei, Y.: Introduction to Combinatorial Testing. CRC Press, Boca Raton (2013) · Zbl 1272.68004
[31] 31. Lei, Y., Tai, K.C.: In-parameter-order: a test generation strategy for pairwise testing. In: Third IEEE International Proceedings High-Assurance Systems Engineering Symposium, pp. 254-261 (1998)
[32] 32. Lei, Y., Kacker, R., Kuhn, D.R., Okun, V., Lawrence, J.: IPOG: a general strategy for t-way software testing. In: 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS’07), pp. 549-556 (2007)
[33] 33. Nurmela, K.J.: Upper bounds for covering arrays by tabu search. Discret. Appl. Math. 138 (1), 143-152 (2004) · Zbl 1034.05013
[34] 34. Raaphorst, S., Moura, L., Stevens, B.: A construction for strength-3 covering arrays from linear feedback shift register sequences. Des. Codes Cryptogr. 73 (3), 949-968 (2014) · Zbl 1297.05040
[35] 35. Seroussi, G., Bshouty, N.H.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inf. Theory 34 (3), 513-522 (1988) · Zbl 0653.94025
[36] 36. Shorin, V.V., Loidreau, P.: Application of Groebner bases techniques for searching new sequences with good periodic correlation properties. In: Proceedings International Symposium on Information Theory (ISIT), pp. 1196-1200 (2005)
[37] 37. Torres-Jimenez, J., Izquierdo-Marquez, I.: Survey of covering arrays. In: 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 20-27 (2013)
[38] 38. Torres-Jimenez, J., Rodriguez-Tello, E.: New bounds for binary covering arrays using simulated annealing. Inf. Sci. 185 (1), 137-152 (2012)
[39] 39. Torres-Jimenez, J., Izquierdo-Marquez, I., Gonzalez-Gomez, A., Avila-George, H.: A branch & bound algorithm to derive a direct construction for binary covering arrays. In: Advances in Artificial Intelligence and Soft Computing, pp. 158-177. Springer, New York (2015)
[40] 40. Yan, J., Zhang, J.: Backtracking algorithms and search heuristics to generate test suites for combinatorial testing. In: 30th Annual International Computer Software and Applications Conference (COMPSAC’06), vol. 1, pp. 385-394 (2006)
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.