Reformulation for the diagnosis of discrete-event systems

Diagnosis is traditionally defined on a space of hypotheses (typically, all the combinations of zero or more possible faults). In the present paper, we argue that a suitable reformulation of this hypothesis space can lead to more efficient computation of diagnoses, most notably by exploiting opportunities for various forms of model abstraction. The paper focuses on the diagnosis of Discrete Event Systems (DES), although the main ideas apply to diagnosis in general. An important contribution of the paper is the study of several formal properties related to the correctness and precision of the diagnoses obtained through reformulation. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.