Physical Impossibility Instead of Fault Models

Abstract

In this paper we describe the concept of physical impossibility as an alternative to the specification of fault models. These axioms can be used to exclude impossible diagnoses similar to fault models. We show for Horn clause theories while the complexity of finding a first diagnosis is worst-case exponential for fault models, it is polynomial for physical impossibility axioms. Even for the case of finding all diagnoses using physical impossibility axioms instead of fault models is more efficient, although both are exponential in the worst case. These results are used for a polynomial diagnosis and measurement strategy which finds a final sufficient diagnosis.