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