Covering arrays with row limit, CARLs, are a new family of combinatorial objects
which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, 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 with the construction 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)ln(w(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), in the same
way 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.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/34006 |
| Date | 11 December 2012 |
| Creators | Francetic, Nevena |
| Contributors | Mendelsohn, Eric |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0026 seconds