NDLI: Sequence Covering Arrays

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Zhou, Junling Horsley, Daniel Colbourn, Charles J. Chee, Yeow Meng
Copyright Year	2013
Abstract	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 \in \{3,4,5\}$ to demonstrate the utility of the conditional expectation algorithm and the product construction.
Starting Page	1844
Ending Page	1861
Page Count	18
File Format	PDF
ISSN	08954801
DOI	10.1137/120894099
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	27
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-10-28
Access Restriction	Subscribed
Subject Keyword	directed $t$-design Packing and covering covering array Orthogonal arrays, Latin squares, Room squares sequence covering array Other designs, configurations completely scrambling set of permutations Permutations, words, matrices
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in