Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorColbourn, Charles J.en
dc.contributor.authorChee, Yeow Mengen
dc.contributor.authorHorsley, Danielen
dc.contributor.authorZhou, Junlingen
dc.identifier.citationChee, Y. M., Colbourn, C. J., Horsley, D., & Zhou, J. (2013). Sequence covering arrays. SIAM journal on discrete mathematics, 27(4), 1844-1861.en
dc.description.abstractSequential 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.en
dc.relation.ispartofseriesSIAM journal on discrete mathematicsen
dc.rights© 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: []. 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.en
dc.subjectDRNTU::Science::Mathematics::Discrete mathematicsen
dc.titleSequence covering arraysen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Sequence covering arrays.pdf267 kBAdobe PDFThumbnail


checked on Sep 7, 2020


checked on Sep 21, 2020

Page view(s)

checked on Sep 24, 2020


checked on Sep 24, 2020

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.