Asymptotic Size of Covering Arrays: An Application of Entropy Compression

Autor:	Nevena Francetić, Brett Stevens
Rok vydání:	2017
Předmět:	Entropy compression Value (computer science) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Set (abstract data type) Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Alphabet Lovász local lemma Row Mathematics
Zdroj:	Journal of Combinatorial Designs. 25:243-257
ISSN:	1063-8539
DOI:	10.1002/jcd.21553
Popis:	A covering array CA (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 Vt is contained in the set of rows of every N×t subarray of A. The parameter N is called the size of an array and CAN (t,k,v) denotes the smallest N for which a CA (N;t,k,v) exists. It is well known that CAN (t,k,v)=Θ(log2k) [10]. In this paper, we derive two upper bounds on d(t,v)=lim supk→∞ CAN (t,k,v)log2k using an algorithmic approach to the Lovasz local lemma also known as entropy compression.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::43a3229ce394206dab9b7871fc392eb8 https://doi.org/10.1002/jcd.21553 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.