Verification Programs for Abduction
Paolo Liberatore, Francesco M. Donini · 2007
. We call verification the process of finding the actual explanation of a given set of manifestations. We consider an abductive setting, in which explanations are sets of assumptions. To filter out erroneous explanations, a verification program should propose which assumptions to check. Given the abductive setting of manifestations, assumptions, and a theory relating them, we study the complexity of providing a minimal set of assumptions to be checked in order to identify the actual explanation. We study also the case in which assumptions to be checked are given in a tree-like order. 1 INTRODUCTION Abduction [8] has been frequently advocated as a process apt to formalize diagnosis --- i.e., the way reasoning is used when looking for (a set of possible) causes for some observed manifestations [9, 10, 2]. In a diagnostic setting, we are given a set of manifestations M observed in the (mal)functioning of a system, a (usually large) set of assumptions H that may or may not explain M , a...