Test Generation for Model-Based Diagnosis

This article formalises the dual problem to model-based diagnosis (MBD), i.e., generating tests to isolate multiple simultaneous faults. Using a standard propositional MBD framework, we first define a test of minimal size that can isolate multiple simultaneous faults of an arbitrary nature. Second, we prove complexity results for multiple-fault tests of minimal size in propositional system models, showing such problems have complexity similar to those of MBD problems, i.e., complexity at the second level of the polynomial hierarchy.