CAUSES AND EXPLANATIONS IN THE STRUCTURAL-MODEL APPROACH: TRACTABLE CASES
Abtg Wissensbasierte Systeme, Thomas Eiter, Thomas Eiter, Thomas Lukasiewicz, Thomas Lukasiewicz · 2002
Abstract. This paper continues the research on the computational aspects of Halpern and Pearl’s causes and explanations in the structural-model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph. Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph, respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structurebased causes and explanations in first-order reasoning about actions, which produces large causal