[1] Zha Rijun, Zhang Deping, Xu Baowen,. Recursive constructions for t-covering arrays [J]. Journal of Southeast University (English Edition), 2011, 27 (3): 340-342. [doi:10.3969/j.issn.1003-7985.2011.03.022]

Copy

Recursive constructions for t-covering arrays()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

27

Issue:

2011 3

Page:

340-342

Research Field:

Computer Science and Engineering

Publishing date:

2011-09-30

Info

Title:

Recursive constructions for t-covering arrays

Author(s):

Zha Rijun¹;  Zhang Deping²;  Xu Baowen³

¹School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
² College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
³Stat

Keywords:

covering array;  orthogonal array;  difference matrix

PACS:

TP306

DOI:

10.3969/j.issn.1003-7985.2011.03.022

Abstract:

A t-covering array of size N, degree k, order v and strength t is an N×k array with entries from a set of v symbols such that any N×t subarray contains a t-tuple of v symbols at least once as a row. This paper presents a new algebraic recursive method for constructing covering arrays based on difference matrices. The method can extend parameter factors on the existing covering arrays and cover all the combinations of any t parameter factors(t≥2).The method, which recursively generates high strength covering arrays, is practical. Meanwhile, the theoretical derivation and realization of the proposed algebraic recursive algorithm are given.

References:

[1] Hartman A. Software and hardware testing using combinatorial covering suites[J]. Graph Theory, Combinatorics and Algorithms, 2005, 34(1):237-266.
[2] Xu Baowen, Nie Changhai, Shi Liang, et al. A software failure debugging method based on combinatorial design approach for testing[J]. Chinese Journal of Computers, 2006, 29(1): 132-138.
[3] Sloane N J A. Covering arrays and intersecting codes[J]. Journal of Combinatorial Designs, 1993, 1(1):51-63.
[4] Colbour C J. Strength two covering arrays: existence tables and projection[J]. Discrete Mathematics, 2008, 308(6):772-786.
[5] Chateaunenf M, Colbour C J, Kreher D L. Covering arrays of strength three[J]. Designs, Codes and Cryptography, 1999, 16(3): 235-242.
[6] Chateaunenf M, Kreher D L. On the state of strength three covering arrays[J]. Journal of Combinatorial Designs, 2002, 10(4):217-238.
[7] Walker Ⅱ R A, Colbourn C J. Tabu search for covering arrays using permutation vectors[J]. Journal of Statistical Planning and Inference, 2009, 139(1):69-80.
[8] Godbole A P, Skipper D E, Sunley R A. T-covering arrays: upper bounds and Poission approximations[J]. Combinatorics, Probability and Computing, 1996, 5(1): 105-117.
[9] Martirosyan S, van Trung T. On t-covering arrays[J]. Designs, Codes and Cryptography, 2004, 32(1):323-339.
[10] Bryce R C, Colbourn C J. A density-based greedy algorithm for higher strength covering arrays[J]. Software Testing, Verification and Reliability, 2009, 19(1):37-53.
[11] Lei Y, Kacker R, Kuhn R D, et al. IPOG: a general strategy for t-way software testing[C]//Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems. Tucson, Arizona, USA, 2007:549-556.
[12] Hedayat A S, Sloane N J A, Stufken J. Orthogonal arrays: theory and applications[M]. New York: Springer, 1999.

Memo

Memo:

Biographies: Zha Rijun(1971—), male, graduate; Xu Baowen(corresponding author), male, doctor, professor, bwxu@nju.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.90818027, 61003020, 91018005, 60873050), the National High Technology Research and Development Program of China(863 Program)(No.2009AA01Z147), the National Basic Research Program of China(973 Program)(No.2009CB320703).
Citation: Zha Rijun, Zhang Deping, Xu Baowen. Recursive constructions for t-covering arrays [J].Journal of Southeast University(English Edition), 2011, 27(3):340-342.[doi:10.3969/j.issn.1003-7985.2011.03.022]

Common functions