Paper Info
Title
Constraint-based optimal testing using DNNF graphs
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 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.
Year
DOI
Venue
2009
10.1007/978-3-642-04244-7_57
CP
Keywords
Field
DocType
input pattern,constraint-based optimal testing,dnnf graph,optimal distinguishing test,real-world application show,finding odts,non-deterministic system,testing problem,compact graphical representation,constraint-based odt generation,decomposable negation normal form,distinguishing test,linear time
Discrete mathematics,Graph,Negation normal form,Computer science,Constraint theory,Algorithm,Time complexity,Medical diagnosis,Computer programming,Distributed computing
Conference
Volume
ISSN
ISBN
5732
0302-9743
3-642-04243-0
Citations 
PageRank 
References 
0
0.34
12
Authors
3
Name
Order
Citations
PageRank
Anika Schumann110313.12
Martin Sachenbacher214613.96
Jinbo Huang337121.81