Locating one pairwise interaction: Three recursive constructions

Year 2016, Volume: 3 Issue: 3, 127 - 134, 09.08.2016

Charles J. Colbourn Bingli Fan

https://doi.org/10.13069/jacodesmath.17551

Cited By: 5

Abstract

In a complex component-based system, choices (levels) for components (factors) may interact to
cause faults in the system behaviour. When faults may be caused by interactions among few factors
at specific levels, covering arrays provide a combinatorial test suite for discovering the presence of
faults. While well studied, covering arrays do not enable one to determine the specific levels of factors
causing the faults; locating arrays ensure that the results from test suite execution suffice to determine
the precise levels and factors causing faults, when the number of such causes is small. Constructions
for locating arrays are at present limited to heuristic computational methods and quite specific direct
constructions. In this paper three recursive constructions are developed for locating arrays to locate
one pairwise interaction causing a fault.

References

• A. N. Aldaco, C. J. Colbourn, V. R. Syrotiuk, Locating arrays: A new experimental design for screening complex engineered systems, SIGOPS Oper. Syst. Rev. 49(1) (2015) 31–40.
• M. Chateauneuf, D. L. Kreher, On the state of strength-three covering arrays, J. Combin. Des. 10(4) (2002) 217–238.
• M. B. Cohen, C. J. Colbourn, A. C. H. Ling, Constructing strength three covering arrays with augmented annealing, Discrete Math. 308(13) (2008) 2709–2722.
• C. J. Colbourn, Covering arrays and hash families, Information Security and Related Combinatorics, NATO Peace and Information Security, IOS Press (2011), 99–136.
• C. J. Colbourn, S. S. Martirosyan, G. L. Mullen, D. Shasha, G. B. Sherwood, J. L. Yucas, Products of mixed covering arrays of strength two, J. Combin. Des. 14(2) (2006) 124–138.
• C. J. Colbourn, S. S. Martirosyan, T. van Trung, R. A. Walker II, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Cryptogr. 41(1) (2006) 33–57.
• C. J. Colbourn, D. W. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim. 15(1) (2008) 17–48.
• A. Hartman, Software and hardware testing using combinatorial covering suites, Graph Theory, Combinatorics and Algorithms, Springer, 2005, 237–266.
• C. Martínez, L. Moura, D. Panario, B. Stevens, Locating errors using ELAs, covering arrays, and adaptive testing algorithms, SIAM J. Discrete Math. 23(4) (2009/10) 1776–1799.
• G. Roux, k-Propriétés dans les tableaux de n colonnes: cas particulier de la k-surjectivité et de la k-permutivité, Ph.D. Dissertation, University of Paris 6, 1987.
• C. Shi, Y. Tang, J. Yin, Optimal locating arrays for at most two faults, Sci. China Math. 55(1) (2012) 197–206.
• Y. Tang, C. J. Colbourn, J. Yin, Optimality and constructions of locating arrays, J. Stat. Theory Pract. 6(1) (2012) 20–29.
• J. Yin, Cyclic difference packing and covering arrays, Des. Codes Cryptogr. 37(2) (2005) 281–292.