TY - GEN

T1 - Constraint-based optimal testing using dnnf graphs

AU - Schumann, Anika

AU - Sachenbacher, Martin

AU - Huang, Jinbo

PY - 2009

Y1 - 2009

N2 - 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 constraint-based ODT generation, which uses structural properties of the system to limit the complexity of computation. 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.

AB - 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 constraint-based ODT generation, which uses structural properties of the system to limit the complexity of computation. 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.

KW - Algorithms

KW - Applications

KW - DNNF graphs

KW - Testing

UR - http://www.scopus.com/inward/record.url?scp=70350422668&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04244-7_57

DO - 10.1007/978-3-642-04244-7_57

M3 - Conference contribution

SN - 3642042430

SN - 9783642042430

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 731

EP - 745

BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings

T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009

Y2 - 20 September 2009 through 24 September 2009

ER -