---
title: "Diagnosing Tree-Decomposable Circuits"
authors:
  - "Yousri El Fattah"
  - "Rina Dechter"
doi: ""
url: "https://ijcai.org/proceedings/1995/224"
pdf: "https://ijcai.org/proceedings/1995/0224.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "1742-1748"
track: "Qualitative Reasoning and Diagnosis"
keywords:
---

# Diagnosing Tree-Decomposable Circuits

Yousri El Fattah, Rina Dechter

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 1742-1748.

## 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 c~n 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 minimal-cardinality diagnoses . 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 theN-bit adder, the performance of SAB being linear provides definite advantages as the size of the circuit increases.