Search Advanced

AIMS Mathematics

2024, Volume 9, Issue 12: 34806-34826. doi: 10.3934/math.20241657
Previous Article Next Article
Research article

Separable detecting arrays

  • 1.
    School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai 201209, China
  • 2.
    Graduate School of Information Science and Technology, Osaka University, Suita 565-0871, Japan
  • 3.
    Department of Mathematics, Taizhou University, Taizhou 225300, China
  • Received: 13 October 2024 Revised: 28 November 2024 Accepted: 06 December 2024 Published: 13 December 2024

  • MSC : 05B15, 05B20, 62K15, 94C12

  • This paper aimed to address the issue of potential noise or measurement errors in component-based systems by utilizing separable detecting arrays (SDAs) to identify interaction faults and assess whether the number of faulty interactions exceeded a predefined threshold. In this paper, we established a comprehensive lower bound on the size of SDAs and explored an equivalence between optimum SDAs and orthogonal arrays with specific properties. By leveraging this equivalence, numerous optimum SDAs were derived from known results of orthogonal arrays. Additionally, optimum SDAs constructed from difference matrices (DMs) possessing the 'super-simple' property were presented. Several infinite classes of such DMs were provided. Specifically, the existence of super-simple DMs with four rows was fully determined. Our study's findings offer practical implications for improving the reliability and accuracy of fault detection in component-based systems.

    Citation: Ce Shi, Tatsuhiro Tsuchiya, Chengmin Wang. Separable detecting arrays[J]. AIMS Mathematics, 2024, 9(12): 34806-34826. doi: 10.3934/math.20241657

    Related Papers:

  • This paper aimed to address the issue of potential noise or measurement errors in component-based systems by utilizing separable detecting arrays (SDAs) to identify interaction faults and assess whether the number of faulty interactions exceeded a predefined threshold. In this paper, we established a comprehensive lower bound on the size of SDAs and explored an equivalence between optimum SDAs and orthogonal arrays with specific properties. By leveraging this equivalence, numerous optimum SDAs were derived from known results of orthogonal arrays. Additionally, optimum SDAs constructed from difference matrices (DMs) possessing the 'super-simple' property were presented. Several infinite classes of such DMs were provided. Specifically, the existence of super-simple DMs with four rows was fully determined. Our study's findings offer practical implications for improving the reliability and accuracy of fault detection in component-based systems.



    加载中


    [1] R. Bose, K. Bush, Orthogonal arrays of strength two and three, Ann. Math. Statist., 23 (1952), 508–524. https://doi.org/10.1214/aoms/1177729331 doi: 10.1214/aoms/1177729331
    [2] M. Buratti, Recursive constructions for difference matrices and relative difference families, J. Comb. Des., 6 (1998), 165–182. https://doi.org/10.1002/(sici)1520-6610(1998)6:3<165::aid-jcd1>3.0.co;2-d doi: 10.1002/(sici)1520-6610(1998)6:3<165::aid-jcd1>3.0.co;2-d
    [3] Y. Chang, C. Colbourn, A. Gowty, D. Horsley, J. Zhou, New bounds on the maximum size of Sperner partition systems, Eur. J. Combin., 90 (2020), 103165. https://doi.org/10.1016/j.ejc.2020.103165 doi: 10.1016/j.ejc.2020.103165
    [4] M. Chateauneuf, C. Colbourn, D. Kreher, Covering arrays of strength three, Des. Codes Cryptogr., 16 (1999), 235–242. https://doi.org/10.1023/A:1008379710317 doi: 10.1023/A:1008379710317
    [5] M. Chateauneuf, D. Kreher, On the state of strength three covering arrays, J. Comb. Des., 10 (2002), 217–238. https://doi.org/10.1002/jcd.10002 doi: 10.1002/jcd.10002
    [6] Y. Chen, Constructions of optimal detecting arrays of degree 5 and strength 2, M.Sc Thesis, Soochow University, 2011.
    [7] C. Colbourn, Strength two covering arrays: existence tables and projection, Discrete Math., 308 (2008), 772–786. https://doi.org/10.1016/j.disc.2007.07.050 doi: 10.1016/j.disc.2007.07.050
    [8] C. Colbourn, CRC handbook of combinatorial designs, New York: CRC Press, 1996. https://doi.org/10.1201/9781003040897
    [9] C. Colbourn, S. Martirosyan, T. Trung, R. Walker Ⅱ, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Cryptogr., 41 (2006), 33–57. https://doi.org/10.1007/s10623-006-0020-8 doi: 10.1007/s10623-006-0020-8
    [10] C. Colbourn, D. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim., 15 (2008), 17–48. https://doi.org/10.1007/s10878-007-9082-4 doi: 10.1007/s10878-007-9082-4
    [11] C. Colbourn, V. Syrotiuk, Detecting arrays for main effects, In: Algebraic informatics, Cham: Springer, 2019,112–123. https://doi.org/10.1007/978-3-030-21363-3_10
    [12] C. Colbourn, V. Syrotiuk, Detecting arrays for effects of single factor, In: European congress of mathematics, Berlin: EMS Press, 2023,693–718. https://doi.org/10.4171/8ecm/19
    [13] D. Drake, Partial $\lambda$-geometries and generalized Hadamard matrices over groups, Can. J. Math., 31 (1979), 617–627. https://doi.org/10.4153/CJM-1979-062-1 doi: 10.4153/CJM-1979-062-1
    [14] A. El-Mesady, Y. Hamed, K. Abualnaja, A novel application on mutually orthogonal graph squares and graph-orthogonal arrays, AIMS Mathematics, 7 (2022), 7349–7373. https://doi.org/10.3934/math.2022410 doi: 10.3934/math.2022410
    [15] G. Ge, On $(g, 4; 1)$-difference matrices, Discrete Math., 301 (2005), 164–174. https://doi.org/10.1016/j.disc.2005.07.004 doi: 10.1016/j.disc.2005.07.004
    [16] A. Gowty, D. Horsley, More constructions for Sperner partition systems, J. Comb. Des., 29 (2021), 579–606. https://doi.org/10.1002/jcd.21780 doi: 10.1002/jcd.21780
    [17] S. Hartman, On simple and supersimple transversal designs, J. Comb. Des., 8 (2000), 311–320. https://doi.org/10.1002/1520-6610(2000)8:5<311::aid-jcd1>3.0.co;2-1 doi: 10.1002/1520-6610(2000)8:5<311::aid-jcd1>3.0.co;2-1
    [18] A. Hartman, L. Raskin, Problems and algorithms for covering arrays, Discrete Math., 284 (2004), 149–156. https://doi.org/10.1016/j.disc.2003.11.029 doi: 10.1016/j.disc.2003.11.029
    [19] A. Hedayat, J. Stufken, G. Su, On difference schemes and orthogonal arrays of strength $t$, J. Stat. Plan. Infer., 56 (1996), 307–324. https://doi.org/10.1016/s0378-3758(96)00026-2 doi: 10.1016/s0378-3758(96)00026-2
    [20] M. Higazy, A. El-Mesady, M. Mohamed, On graph-orthogonal arrays by mutually orthogonal graph squares, Symmetry, 12 (2020), 1895. https://doi.org/10.3390/sym12111895 doi: 10.3390/sym12111895
    [21] A. Hedayat, N. Sloane, J. Stufken, Orthogonal array: theory and applications, New York: Springer, 1999. http://dx.doi.org/10.1007/978-1-4612-1478-6
    [22] L. Ji, J. Yin, Constructions of new orthogonal arrays and covering arrays of strength three, J. Comb. Theory A, 117 (2010), 236–247. https://doi.org/10.1016/j.jcta.2009.06.002 doi: 10.1016/j.jcta.2009.06.002
    [23] L. Jiang, C. Shi, A construction of variable strength covering arrays, Acta Math. Appl. Sin. Engl. Ser., 37 (2021), 240–250. https://doi.org/10.1007/s10255-021-1006-z doi: 10.1007/s10255-021-1006-z
    [24] D. Kuhn, R. Kacker, Y. Lei, Introduction to combinatorial testing, Boca Raton: Chapman & Hall/CRC, 2013.
    [25] D. Kuhn, M. Reilly, An investigation of the applicability of design of experiments to software testing, Proceedings of 27th Annual NASA Goddard/IEEE Software Engineering Workshop, 2002, 91–95. https://doi.org/10.1109/sew.2002.1199454 doi: 10.1109/sew.2002.1199454
    [26] D. Kuhn, D. Wallace, A. Gallo, Software fault interactions and implications for software testing, IEEE T. Software Eng., 30 (2004), 418–421. https://doi.org/10.1109/TSE.2004.24 doi: 10.1109/TSE.2004.24
    [27] P. Li, K. Meagher, Sperner partition systems, J. Comb. Des., 21 (2013), 267–279. https://doi.org/10.1002/jcd.21330 doi: 10.1002/jcd.21330
    [28] K. Meagher, L. Moura, B. Stevens, A Sperner-type theorem for set-partition systems, Electron. J. Combin., 12 (2005), 20. https://doi.org/10.37236/1987 doi: 10.37236/1987
    [29] C. Nie, H. Leung, A survey of combinatorial testing, ACM Comput. Surv., 43 (2011), 11. https://doi.org/10.1145/1883612.1883618 doi: 10.1145/1883612.1883618
    [30] R. Pan, Y. Chang, A note on difference matrices over non-cyclic finite abelian groups, Discrete Math., 339 (2016), 822–830. https://doi.org/10.1016/j.disc.2015.10.028 doi: 10.1016/j.disc.2015.10.028
    [31] K. Sarkar, C. Colbourn, Two-stage algorithms for covering array construction, J. Comb. Des., 27 (2019), 475–505. https://doi.org/10.1002/jcd.21657 doi: 10.1002/jcd.21657
    [32] E. Seiden, On the problem of construction of orthogonal arrays, Ann. Math. Statist., 25 (1954), 151–156. https://doi.org/10.1214/aoms/1177728855 doi: 10.1214/aoms/1177728855
    [33] S. Seidel, K. Sarkar, C. Colbourn, V. Syrotiuk, Separating interaction effects using locating and detecting arrays, In: Combinatorial algorithms, Cham: Springer, 2018,349–360. https://doi.org/10.1007/978-3-319-94667-2_29
    [34] C. Shi, Optimum super-simple mixed covering arrays of type $a^1b^{k-1}$, Acta Math. Sin.-English Ser., 33 (2017), 153–164. https://doi.org/10.1007/s10114-017-5684-7 doi: 10.1007/s10114-017-5684-7
    [35] C. Shi, L. Jiang, A. Tao, Consecutive detecting arrays for interaction faults, Graph. Combinator., 36 (2020), 1203–1218. https://doi.org/10.1007/s00373-020-02176-7 doi: 10.1007/s00373-020-02176-7
    [36] C. Shi, Y. Tang, J. Yin, The equivalence between optimal detecting arrays and super-simple OAs, Des. Codes Cryptogr., 62 (2012), 131–142. https://doi.org/10.1007/s10623-011-9498-9 doi: 10.1007/s10623-011-9498-9
    [37] C. Shi, Y. Tang, J. Yin, Optimum mixed level detecting arrays, Ann. Statist., 42 (2014), 1546–1563. https://doi.org/10.1214/14-AOS1228 doi: 10.1214/14-AOS1228
    [38] C. Shi, A. Tao, Consecutive detecting arrays from m-sequence, IAENG International Journal of Applied Mathematics, 50 (2020), 80–86.
    [39] C. Shi, C. Wang, Optimum detecting arrays for independent interaction faults, Acta Math. Sin.-English Ser., 32 (2016), 199–212. https://doi.org/10.1007/s10114-016-5049-7 doi: 10.1007/s10114-016-5049-7
    [40] C. Shi, J. Yin, Existence of super-simple OA$_\lambda(3, 5, v)$'s, Des. Codes Cryptogr., 72 (2014), 369–380. https://doi.org/10.1007/s10623-012-9771-6 doi: 10.1007/s10623-012-9771-6
    [41] Y. Tang, J. Yin, Detecting arrays and their optimality, Acta. Math. Sin.-English Ser., 27 (2011), 2309–2318. https://doi.org/10.1007/s10114-011-0184-7 doi: 10.1007/s10114-011-0184-7
    [42] G. Tzanakis, L. Moura, D. Panario, B. Stevens, Covering arrays from $m$-sequences and character sums, Des. Codes Cryptogr., 85 (2017), 437–456. https://doi.org/10.1007/s10623-016-0316-2 doi: 10.1007/s10623-016-0316-2
    [43] Y. Zang, G. Chen, K. Chen, Z. Tian, Further results on 2-uniform states arising from Irredundant orthogonal arrays, Adv. Math. Commun., 16 (2022), 231–247. https://doi.org/10.3934/amc.2020109 doi: 10.3934/amc.2020109
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(178) PDF downloads(31) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog