Diagnosing tree-structured systems

This paper introduces the TREE/TREE* algorithm for computing minimal diagno ses for tree-structured systems. Diagnoses are computed by descending into the tree, enumerating the input combinations that might be responsible for a given incorrect observation, and combining the diagnoses for the subtrees generating these inputs into diagnoses for the whole system. Algorithm TRE E diagnoses systems containing functional components and algorithm TREE* di agnoses more general constraint-based components. We prove soundness and co rrectness of the algorithms and show experimental results that indicate tha t they compare favorably to Reiter's hitting-set-based algorithm and El Fat tah and Dechter's SAB. Extensions of the algorithms such as use of fault mo des are discussed. (C) 2001 Elsevier Science B.V. All rights reserved.