Error Locating Arrays, Adaptive Software Testing, and Combinatorial Group Testing

Content Provider	Semantic Scholar
Author	Chodoriwsky, Jacob
Copyright Year	2012
Abstract	Combinatorial Group Testing (CGT) is a process of identifying faulty interactions (“errors”) within a particular set of items. Error Locating Arrays (ELAs) are combinatorial designs that can be built from Covering Arrays (CAs) to not only cover all errors in a system (each involving up to a certain number of items), but to locate and identify the errors as well. In this thesis, we survey known results for CGT, as well as CAs, ELAs, and some other types of related arrays. More importantly, we give several new results. First, we give a new algorithm that can be used to test a system in which each component (factor) has two options (values), and at most two errors are present. We show that, for systems with at most two errors, our algorithm improves upon a related algorithm by Martinez et al. [32] in terms of both robustness and efficiency. Second, we give the first adaptive CGT algorithm that can identify, among a given set of k items, all faulty interactions involving up to three items. We then compare it, performance-wise, to current-best nonadaptive method that can identify faulty interactions involving up to three items. We also give the first adaptive ELAbuilding algorithm that can identify all faulty interactions involving up to three items when safe values are known. Both of our new algorithms are generalizations of ones previously given by Martinez et al. [32] for identifying all faulty interactions involving up to two items.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www.site.uottawa.ca/~lucia/grads/jacob/JacobThesis.pdf
Alternate Webpage(s)	https://ruor.uottawa.ca/bitstream/10393/23083/1/Chodoriwsky_Jacob_2012_thesis.pdf
Alternate Webpage(s)	https://doi.org/10.20381/ruor-5890
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article