Name
Abstract | ||
|---|---|---|
The goal of testing is to distinguish between a number of hypotheses about a system-for example, different diagnoses of faults-by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Optimal distinguishing tests (ODTs) are those input patterns that are most likely to distinguish between hypotheses about non-deterministic systems. Finding ODTs is practically important, but it amounts in general to determining a ratio of model counts and is therefore computationally very expensive. In this paper, we present a novel approach to this problem, which uses structural properties of the system to limit the complexity of computing ODTs. We first construct a compact graphical representation of the testing problem via compilation into decomposable negation normal form. Based on this compiled representation, we show how one can evaluate distinguishing tests in linear time, which allows us to efficiently determine an ODT. Experimental results from a real-world application show that our method can compute ODTs for instances that were intractable for previous approaches. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.entcs.2009.09.053 | Electr. Notes Theor. Comput. Sci. |
Keywords | DocType | Volume |
input pattern,optimal distinguishing test,real-world application show,dnnf graphs,non-deterministic systems,model counting,decomposable negation normal form,different diagnosis,finding odts,testing problem,testing,compact graphical representation,computing optimal tests,distinguishing test,linear time | Journal | 253 |
Issue | ISSN | Citations |
2 | Electronic Notes in Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.36 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anika Schumann | 1 | 103 | 13.12 |
| Martin Sachenbacher | 2 | 146 | 13.96 |
| Jinbo Huang | 3 | 371 | 21.81 |