Grant: Discovery Grants Program - Individual

This research proposal focuses on the theory and application of certain combinatorial designs called covering arrays and cover-free families. They are used in coding theory, an area of research that deals with the detection and correction of errors in communication, where they are called surjective arrays and superimposed codes, respectively. They have been used in combinatorial interaction testing, combinatorial group testing, as well as in cryptography and communications. Covering arrays are useful in software testing as they guarantee good coverage of the software input parameter space, enabling the detection of errors in software with a reduced number of tests. The software testing community refers to this approach as pairwise testing or t-way testing. More generally, covering arrays can be used to test any black-box system (e.g. software, hardware, network) whose behaviour depends on input parameters with a finite number of values. Cover-free families are used in combinatorial group testing, where the goal is to determine a set of defective items among a set of items using a small number of tests in parallel (non-adaptive group testing). Their typical application is pooled testing for disease screening, where samples from individuals are combined into a number of pools that are tested to detect the infected individuals, while minimizing the total number of tests. Here, we refer to both types of designs as covering arrays. Now, in some cases, these covering arrays are covering more than is necessary to accomplish the error location at hand. We suggest that by requiring "just enough coverage" we can reduce the number of tests. This means less resources would be needed to test a piece of software or shorter time would be required to screen a community for sick individuals. This "just enough coverage" can be specified by what we call a hypergraph. We will research how to efficiently build covering arrays based on hypergraphs to make testing faster. For this, we need to develop some combinatorial theory and some algorithmic constructions. In software testing and disease screening, researchers have already identified situations where the hypergraph model applies, but further research is necessary to enable their use in applications. This research proposal focuses on constructing covering arrays based on hypergraphs by developing the theory needed for their efficient construction, with the final goal of using them in applications.