R27  
Diagnosing TreeDecomposable Curcuits
Yousri El Fattah (fattah@ics.uci.edu) &
Rina Dechter (dechter@ics.uci.edu)

Abstract This paper describes a diagnosis algorithm called structurebased abduction (SAB) which was developed in the framework of costraint networks [12]. The algorithm exploits the structure of the constraint network and is most efficient for neartree problem domains. By analyzing the structure of the problem domain, the performance of such algorithms can be bounded in advance. We present empirical results comparing SAB with two modelbased algorithms, MBD1 and MBD2, for the task of finding one or all minimalcardinality diagnosis. MBD1 uses the same computing strategy as algorithm GDE [9]. MBD2 adopts a breadthfirst search strategy similar to the algorithm DIAGNOSE [24]. The main conclusion is that for nearly acyclic circuits, such as the Nbit adder, the performance of SAB being linear provides definite advantages as the size of the circuit increases. [ps] [pdf] 