Algebraic Models for Arbitrary Strength Covering Arrays over v-ary Alphabets | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algebraic Models for Arbitrary Strength Covering Arrays over v-ary Alphabets

  • Conference paper
  • First Online:
Algebraic Informatics (CAI 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11545))

Included in the following conference series:

Abstract

Extending our previous work [7], we introduce a novel technique to model and compute arbitrary strength covering arrays over v-ary alphabets, using methods arising from linear algebra commutative algebra and symbolic computation. Concrete instances of covering arrays for given parameters then appear as points in varieties as they occur in solutions of multivariate polynomial equation systems. To solve these systems we apply polynomial solvers based on the theory of Gröbner bases and exhaustive search using serial and parallel programming techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://docs.computecanada.ca/wiki/Graham.

References

  1. Bryce, R.C., Colbourn, C.J.: A density-based greedy algorithm for higher strength covering arrays. Softw. Test. Verif. Reliab. 19(1), 37–53 (2009)

    Article  Google Scholar 

  2. 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)

    Article  MathSciNet  Google Scholar 

  3. Bush, K.A., et al.: Orthogonal arrays of index unity. Ann. Math. Stat. 23(3), 426–434 (1952)

    Article  MathSciNet  Google Scholar 

  4. Colbourn, C.J.: Combinatorial aspects of covering arrays. Le Mathematiche 59(1, 2), 125–172 (2004)

    MathSciNet  MATH  Google Scholar 

  5. Colbourn, C.J., Dinitz, J.H.: Handbook of Combinatorial Designs. CRC Press, Boca Raton (2006)

    Book  Google Scholar 

  6. Danziger, P., Mendelsohn, E., Moura, L., Stevens, B.: Covering arrays avoiding forbidden edges. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 296–308. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85097-7_28

    Chapter  Google Scholar 

  7. Garn, B., Simos, D.E.: Algebraic modelling of covering arrays. In: Kotsireas, I.S., Martínez-Moro, E. (eds.) ACA 2015. PROMS, vol. 198, pp. 149–170. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56932-1_10

    Chapter  MATH  Google Scholar 

  8. Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test problem. Constraints 11(2), 199–219 (2006)

    Article  MathSciNet  Google Scholar 

  9. Kampel, L., Simos, D.E.: A survey on the state of the art of complexity problems for covering arrays. Theoret. Comput. Sci. (2018, to appear)

    Google Scholar 

  10. Kleitman, D.J., Spencer, J.: Families of k-independent sets. Discrete Math. 6(3), 255–262 (1973)

    Article  MathSciNet  Google Scholar 

  11. Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search, 1st edn. CRC Press, Boca Raton (1998)

    MATH  Google Scholar 

  12. Kuhn, D., Kacker, R., Lei, Y.: Introduction to Combinatorial Testing. Chapman & Hall/CRC Innovations in Software Engineering and Software Development Series. Taylor & Francis, London (2013)

    MATH  Google Scholar 

  13. Kuhn, R., Kacker, R., Lei, Y., Hunter, J.: Combinatorial software testing. Computer 42(8), 94–96 (2009)

    Article  Google Scholar 

  14. Lei, Y., Tai, K.C.: In-parameter-order: a test generation strategy for pairwise testing. In: Proceedings of the Third IEEE International High-Assurance Systems Engineering Symposium (Cat. No. 98EX231), pp. 254–261 (1998)

    Google Scholar 

  15. Nayeri, P., Colbourn, C.J., Konjevod, G.: Randomized post-optimization of covering arrays. Eur. J. Comb. 34(1), 91–103 (2013)

    Article  MathSciNet  Google Scholar 

  16. Seroussi, G., Bshouty, N.H.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inf. Theory 34(3), 513–522 (1988)

    Article  MathSciNet  Google Scholar 

  17. Torres-Jimenez, J., Izquierdo-Marquez, I.: Survey of covering arrays. In: 2013 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 20–27 (2013)

    Google Scholar 

Download references

Acknowledgements

This research was carried out partly in the context of the Austrian COMET K1 program and publicly funded by the Austrian Research Promotion Agency (FFG) and the Vienna Business Agency (WAW). Kotsireas and Zhereshchin are supported by an NSERC grant.

Author information

Authors and Affiliations

  1. SBA Research, 1040, Vienna, Austria

    Ludwig Kampel, Dimitris E. Simos & Bernhard Garn

  2. CARGO Lab, Wilfrid Laurier University, Waterloo, ON, Canada

    Ilias S. Kotsireas & Evgeny Zhereshchin

Authors
  1. Ludwig Kampel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dimitris E. Simos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bernhard Garn
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ilias S. Kotsireas
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Evgeny Zhereshchin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dimitris E. Simos .

Editor information

Editors and Affiliations

  1. University of Niš, Niš, Serbia

    Miroslav Ćirić

  2. University of Leipzig , Leipzig, Germany

    Manfred Droste

  3. Université Paris Denis Diderot and CNRS, Paris, France

    Jean-Éric Pin

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kampel, L., Simos, D.E., Garn, B., Kotsireas, I.S., Zhereshchin, E. (2019). Algebraic Models for Arbitrary Strength Covering Arrays over v-ary Alphabets. In: Ćirić, M., Droste, M., Pin, JÉ. (eds) Algebraic Informatics. CAI 2019. Lecture Notes in Computer Science(), vol 11545. Springer, Cham. https://doi.org/10.1007/978-3-030-21363-3_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-21363-3_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-21362-6

  • Online ISBN: 978-3-030-21363-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation