The effect of observations on the complexity of model-based diagnosis
Adnan Y. Darwiche, Gregory M. Provan · 1997
This paper shows how to efficiently diagnose systems by making use of observations. In particular, we present two theorems concerning the effect of observations on the complexity of Model--Based Diagnosis. The first theorem shows how the presence of certain observations allows us to decompose a diagnostic reasoning task into independent reasoning tasks on subsystems. The second theorem shows how the absence of certain observations allows us to ignore parts of a system during diagnostic reasoning. Another main contribution of this paper is an application of these theorems to diagnosing discrete--event systems. In particular, we identify observability and modularity characteristics of discrete--event systems that make them amenable to the presented theorems and, hence, to any diagnostic approach that employs these theorems effectively. This also explains why a particular approach that we have presented elsewhere has proven effective for diagnosing these systems. Introduction This paper ...