Abductive reasoning through filtering

Abduction is an inference mechanism where given a knowledge base and some o bservations, the reasoner tries to find hypotheses which together with the knowledge base explain the observations. A reasoning based on such an infer ence mechanism is referred to as abductive reasoning. Given a theory and so me observations, by filtering the theory with the observations, we mean sel ecting only those models of the theory that entail the observations. Entail ment with respect to these selected models is referred to as filter entailm ent. In this paper we give necessary and sufficient conditions when abducti ve reasoning with respect to a theory and some observations is equivalent t o the corresponding filter entailment. We then give sufficiency conditions for particular knowledge representation formalisms that guarantee that abdu ctive reasoning can indeed be done through filtering and present examples f rom the knowledge representation literature where abductive reasoning is do ne through filtering. We extend the notions of abductive reasoning and filt er entailment to allow preferences among explanations and models respective ly and give conditions when they are equivalent. Finally, we give a weaker notion of abduction and abductive reasoning and show the later to be equiva lent to filter entailment under less restrictive conditions. (C) 2000 Elsev ier Science B.V. All rights reserved.