Everyone welcome. Refreshments will be served in the Math Lounge before the exam.
Tuesday, May 29, 2012, 10:10 a.m., in BA 6183, 40 St. George Street
PhD Candidate: Nevena Francetic
PhD Advisor: Eric Mendelsohn
Thesis Title: Covering Arrays with Row Limit
(http://www.math.toronto.edu/nfrancet/mojaTeza.pdf)
Thesis Abstract:
Covering arrays with row limit, CARLs for short, are a generalization of group divisible designs and covering arrays. Similarly to their predecessor, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v: w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once.
This thesis is concerned with the bounds on the size and constructions of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)lnw(k) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant.
Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k) = ck, where c < 1. Also, we construct optimal CARLs when t = 2 and w = 4, and prove that there exists a constant δ, such that for any v and k ≥ 4, an optimal CARL(2,k,v: 4) differs from the lower bound by at most δ rows, with some possible exceptions.
Finally, we define a packing array with row limit, PARL(N;t,k,v: w), the same as a CARL(N;t,k,v: w) with the difference that any t-tuple is contained at most once in any N × t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t = 2, we consider a transformation of optimal CARLs with row limit w = 3 to optimal PARLs with w = 3.
no comment as of now