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.