Physical Impossibility Instead of Fault Models

Gerhard Friedrich, Georg Gottlob, Wolfgang Nejdl

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.