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

Full description

Saved in:
Bibliographic Details
Main Authors: Colbourn, Charles J., Chee, Yeow Meng, Horsley, Daniel, Zhou, Junling
Other Authors: School of Physical and Mathematical Sciences
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