Premium
Asymptotic Size of Covering Arrays: An Application of Entropy Compression
Author(s) -
Francetić Nevena,
Stevens Brett
Publication year - 2017
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21553
Subject(s) - mathematics , combinatorics , alphabet , row , lemma (botany) , entropy (arrow of time) , upper and lower bounds , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , ecology , philosophy , linguistics , physics , poaceae , quantum mechanics , database , biology , programming language
A covering arrayCA ( N ; t , k , v ) is an N × k array A such that each cell of A takes a value from a v ‐set V , which is called the alphabet. Moreover, the set V t is contained in the set of rows of every N × t subarray of A . The parameter N is called the size of an array andCAN ( t , k , v ) denotes the smallest N for which aCA ( N ; t , k , v ) exists. It is well known thatCAN ( t , k , v ) = Θ ( log 2 k ) [10]. In this paper, we derive two upper bounds on d ( t , v ) = lim sup k → ∞CAN ( t , k , v )log 2 kusing an algorithmic approach to the Lovász local lemma also known as entropy compression.