Model-Based Diagnosis using Structured System Descriptions
  This paper presents a comprehensive approach for model-based diagnosis which
includes proposals for characterizing and computing preferred diagnoses,
assuming that the system description is augmented with a system structure (a
directed graph explicating the interconnections between system components).
Specifically, we first introduce the notion of a consequence, which is a
syntactically unconstrained propositional sentence that characterizes all
consistency-based diagnoses and show that standard characterizations of
diagnoses, such as minimal conflicts, correspond to syntactic variations on a
consequence. Second, we propose a new syntactic variation on the consequence
known as negation normal form (NNF) and discuss its merits compared to standard
variations. Third, we introduce a basic algorithm for computing consequences in
NNF given a structured system description. We show that if the system structure
does not contain cycles, then there is always a linear-size consequence in NNF
which can be computed in linear time. For arbitrary system structures, we show
a precise connection between the complexity of computing consequences and the
topology of the underlying system structure. Finally, we present an algorithm
that enumerates the preferred diagnoses characterized by a consequence. The
algorithm is shown to take linear time in the size of the consequence if the
preference criterion satisfies some general conditions.
