Cargando…
Refining the In-Parameter-Order Strategy for Constructing Covering Arrays
Covering arrays are structures for well-representing extremely large input spaces and are used to efficiently implement blackbox testing for software and hardware. This paper proposes refinements over the In-Parameter-Order strategy (for arbitrary t). When constructing homogeneous-alphabet covering...
Autores principales: | , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
[Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology
2008
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4652878/ https://www.ncbi.nlm.nih.gov/pubmed/27096128 http://dx.doi.org/10.6028/jres.113.022 |
_version_ | 1782401832897740800 |
---|---|
author | Forbes, Michael Lawrence, Jim Lei, Yu Kacker, Raghu N. Kuhn, D. Richard |
author_facet | Forbes, Michael Lawrence, Jim Lei, Yu Kacker, Raghu N. Kuhn, D. Richard |
author_sort | Forbes, Michael |
collection | PubMed |
description | Covering arrays are structures for well-representing extremely large input spaces and are used to efficiently implement blackbox testing for software and hardware. This paper proposes refinements over the In-Parameter-Order strategy (for arbitrary t). When constructing homogeneous-alphabet covering arrays, these refinements reduce runtime in nearly all cases by a factor of more than 5 and in some cases by factors as large as 280. This trend is increasing with the number of columns in the covering array. Moreover, the resulting covering arrays are about 5 % smaller. Consequently, this new algorithm has constructed many covering arrays that are the smallest in the literature. A heuristic variant of the algorithm sometimes produces comparably sized covering arrays while running significantly faster. |
format | Online Article Text |
id | pubmed-4652878 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2008 |
publisher | [Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology |
record_format | MEDLINE/PubMed |
spelling | pubmed-46528782016-04-19 Refining the In-Parameter-Order Strategy for Constructing Covering Arrays Forbes, Michael Lawrence, Jim Lei, Yu Kacker, Raghu N. Kuhn, D. Richard J Res Natl Inst Stand Technol Article Covering arrays are structures for well-representing extremely large input spaces and are used to efficiently implement blackbox testing for software and hardware. This paper proposes refinements over the In-Parameter-Order strategy (for arbitrary t). When constructing homogeneous-alphabet covering arrays, these refinements reduce runtime in nearly all cases by a factor of more than 5 and in some cases by factors as large as 280. This trend is increasing with the number of columns in the covering array. Moreover, the resulting covering arrays are about 5 % smaller. Consequently, this new algorithm has constructed many covering arrays that are the smallest in the literature. A heuristic variant of the algorithm sometimes produces comparably sized covering arrays while running significantly faster. [Gaithersburg, MD] : U.S. Dept. of Commerce, National Institute of Standards and Technology 2008 2008-10-01 /pmc/articles/PMC4652878/ /pubmed/27096128 http://dx.doi.org/10.6028/jres.113.022 Text en https://creativecommons.org/publicdomain/zero/1.0/ The Journal of Research of the National Institute of Standards and Technology is a publication of the U.S. Government. The papers are in the public domain and are not subject to copyright in the United States. Articles from J Res may contain photographs or illustrations copyrighted by other commercial organizations or individuals that may not be used without obtaining prior approval from the holder of the copyright. |
spellingShingle | Article Forbes, Michael Lawrence, Jim Lei, Yu Kacker, Raghu N. Kuhn, D. Richard Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title | Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title_full | Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title_fullStr | Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title_full_unstemmed | Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title_short | Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
title_sort | refining the in-parameter-order strategy for constructing covering arrays |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4652878/ https://www.ncbi.nlm.nih.gov/pubmed/27096128 http://dx.doi.org/10.6028/jres.113.022 |
work_keys_str_mv | AT forbesmichael refiningtheinparameterorderstrategyforconstructingcoveringarrays AT lawrencejim refiningtheinparameterorderstrategyforconstructingcoveringarrays AT leiyu refiningtheinparameterorderstrategyforconstructingcoveringarrays AT kackerraghun refiningtheinparameterorderstrategyforconstructingcoveringarrays AT kuhndrichard refiningtheinparameterorderstrategyforconstructingcoveringarrays |