Covering array bounds using analytical techniques

MaRDI QIDQ5251960zbMATH OpenFDO

Authors Ruyue Julia Yuan, Zoe Koch, Anant P. Godbole

Publication date 21 May 2015

Full work available at URL https://arxiv.org/abs/1405.2844

zbMATH Keywords

\(t\)-covering arrayLovász local lemmaStirling's formula

Mathematics Subject Classification ID

Other designs, configurations (05B30)

Abstract: A $t$-covering array with entries from the alphabet $calQ=0,1,ldots,q-1$ is a $kimesn$ stack, so that for any choice of $t$ (typically non-consecutive) columns, each of the $q^t$ possible $t$-letter words over $calQ$ appear at least once among the rows of the selected columns. We will show how a combination of the Lov'asz local lemma; combinatorial analysis; Stirling's formula; and Calculus enables one to find better asymptotic bounds for the minimum size of $t$-covering arrays, notably for $t=3,4$. Here size is measured in the number of rows, as expressed in terms of the number of columns.

Recommendations

• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Upper bounds on the size of covering arrays
• Asymptotic size of covering arrays: an application of entropy compression
• t-covering arrays generated by a tiling probability model
• Small arrays of maximum coverage

Cited in

(9)

• Asymptotic and constructive methods for covering perfect hash families and covering arrays
• The Lovász local lemma and variable strength covering arrays
• Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma
• Small arrays of maximum coverage
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Covering arrays for some equivalence classes of words
• Upper bounds on the size of covering arrays
• Asymptotic size of covering arrays: an application of entropy compression
• t-covering arrays generated by a tiling probability model

This page was built for publication: Covering array bounds using analytical techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251960)