Premium
Covering arrays for some equivalence classes of words
Author(s) -
Cassels Joshua,
Godbole Anant
Publication year - 2019
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.21659
Subject(s) - mathematics , alphabet , combinatorics , partition (number theory) , row , logarithm , equivalence (formal languages) , set (abstract data type) , discrete mathematics , arithmetic , computer science , mathematical analysis , philosophy , linguistics , database , programming language
Covering arrays for words of length t over a d ‐letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the d tt ‐letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case known as partitioning hash families, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weight are equivalent. In both cases, we produce logarithmic upper bounds on the minimum size k = k ( n ) of a covering array. Definitive results for t = 2 , 3 , 4 , as well as general results, are provided.