Model-Based Diagnosis using Structured System Descriptions
<|reference_start|>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.<|reference_end|>
@article{darwiche1998model-based,
    title={Model-Based Diagnosis using Structured System Descriptions},
    author={A. Darwiche},
    journal={Journal of Artificial Intelligence Research, Vol 8, (1998),
  165-222},
    year={1998},
    archivePrefix={arXiv},
    eprint={cs/9806101},
    primaryClass={cs.AI}
}