Abstract
This paper describes a diagnosis algorithm called structure-based 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 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 model-based algorithms, MBD1 and MBD2, for the task of finding one or all minimal-cardinality diagnosis. MBD1 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.