A Measure of Arbitrariness in Abductive Explanations

ABSTRACT. In this paper, we study the framework of abductive logic programming extended with integrity constraints. For this framework, we introduce a new measure of the simplicity of an explanation in terms of its degree of arbitrariness. The more arbitrary the explanation the less appealing it is, with constrained explanations having no arbitrariness and so, being the preferred ones. In the paper, we study basic properties of constrained explanations. For the case when programs in abductive theories are stratified we establish results providing a detailed picture of the complexity of the problem to decide whether constrained explanations exist.