Qualifying the Expressivity/Efficiency Tradeoff: Reformation-Based Diagnosis

Abstract

This paper presents an approach to model-based diagnosis that first compiles a first-order system description to a propositional representation, and then solves the diagnostic problem as a linear programming instance. Relevance reasoning is employed to isolate parts of the system that are related to certain observation types and to economically instantiate the theory, while methods from operations research offer promising results to generate near-optimal diagnoses efficiently. Introduction and Motivation A central problem of model-based diagnosis is the computational complexity of the underlying diagnostic reasoning task (see, e.g. Eiter and Gottlob (1995)). Therefore, several researchers have proposed to preprocess a given system description, mostly a propositional theory, such that the `compiled' form can be processed more efficiently (Williams & Nayak 1996; Darwiche 1998). In many cases, however, it is more natural to describe systems in a more expressive language, such as firstor...