Sequence covering arrays
Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events is ex...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2014
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/101415 http://hdl.handle.net/10220/18653 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-101415 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1014152023-02-28T19:23:00Z Sequence covering arrays Colbourn, Charles J. Chee, Yeow Meng Horsley, Daniel Zhou, Junling School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Discrete mathematics Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on v events for which every subsequence of t or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely t-scrambling set of permutations, in which the images of every set of t chosen events include each of the t! possible “patterns.” In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest v for which the minimum can equal t! is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of v when t is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when t = 3 to construct sequence covering arrays on vw events from ones on v and w events. Finally computational results are given for t ∈ {3,4,5} to demonstrate the utility of the conditional expectation algorithm and the product construction. Published version 2014-01-21T07:53:04Z 2019-12-06T20:38:21Z 2014-01-21T07:53:04Z 2019-12-06T20:38:21Z 2013 2013 Journal Article Chee, Y. M., Colbourn, C. J., Horsley, D., & Zhou, J. (2013). Sequence covering arrays. SIAM journal on discrete mathematics, 27(4), 1844-1861. https://hdl.handle.net/10356/101415 http://hdl.handle.net/10220/18653 10.1137/120894099 en SIAM journal on discrete mathematics © 2013 Society for Industrial and Applied Mathematics. This paper was published in SIAM Journal on Discrete Mathematics and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official DOI: [http://dx.doi.org/10.1137/120894099]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Science::Mathematics::Discrete mathematics |
spellingShingle |
DRNTU::Science::Mathematics::Discrete mathematics Colbourn, Charles J. Chee, Yeow Meng Horsley, Daniel Zhou, Junling Sequence covering arrays |
description |
Sequential processes can encounter faults as a result of improper ordering of subsets
of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for
some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events
is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on
v events for which every subsequence of t or fewer events arises in at least one of the permutations.
Equivalently it is a (different) set of permutations, a completely t-scrambling set of permutations,
in which the images of every set of t chosen events include each of the t! possible “patterns.” In
event sequence testing, minimizing the number of permutations used is the principal objective. By
developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum
number of rows in covering arrays are obtained. An existing bound on the largest v for which the
minimum can equal t! is improved. A conditional expectation algorithm is developed to generate
sequence covering arrays whose number of permutations never exceeds a specified logarithmic function
of v when t is fixed, and this method is shown to operate in polynomial time. A recursive product
construction is established when t = 3 to construct sequence covering arrays on vw events from ones
on v and w events. Finally computational results are given for t ∈ {3,4,5} to demonstrate the utility
of the conditional expectation algorithm and the product construction. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Colbourn, Charles J. Chee, Yeow Meng Horsley, Daniel Zhou, Junling |
format |
Article |
author |
Colbourn, Charles J. Chee, Yeow Meng Horsley, Daniel Zhou, Junling |
author_sort |
Colbourn, Charles J. |
title |
Sequence covering arrays |
title_short |
Sequence covering arrays |
title_full |
Sequence covering arrays |
title_fullStr |
Sequence covering arrays |
title_full_unstemmed |
Sequence covering arrays |
title_sort |
sequence covering arrays |
publishDate |
2014 |
url |
https://hdl.handle.net/10356/101415 http://hdl.handle.net/10220/18653 |
_version_ |
1759856804467048448 |