Diagnosing Tree-Decomposable Circuits

Abstract

This paper describes a diagnosis algorithm called structure-based abduction (SAB) which was developed in the framework of constraint networks [12]. The algorithm exploits the structure of the constraint network and is most efficient for near-tree 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, MBDl and MBD2, for the task of finding one or all minimal-cardinality diagnoses. MBDl uses the same computing strategy as algorithm GDE [9]. MBD2 adopts a breadth-first search strategy similar to the algorithm DIAGNOSE [24]. The main conclusion is that for nearly acyclic circuits, such as the N-bit adder, the performance of SAB being linear provides definite advantages as the size of the circuit increases.