Causal Models of Disjunctive Logic Programs
Pascal Van Hentenryck · 1994
We present a new semantics for disjunctive logic programs. The idea is to extract a class of programs, causal programs, where the disjunction can be simulated by negation-as-failure: disjunctive programs are reduced to stratified nondisjunctive programs by a series of shift-operations. A similar approach has been recently defined by Schaerf and the complexity of testing causality was stated as an open question. We solve this problem by proving its NP-completeness and we give a simple syntactic condition to define a subclass which is polynomial. We define causal models and consider the semantics induced by these models. We show that our causal semantics has very attractive computational behaviour: it belongs to the first level of the polynomial hierarchy unlike the minimal model semantics (GCWA), which is even for positive disjunctive programs IIP2-complete. In addition, causal semantics satisfies interesting abstract properties: it is cumulative and rational. The class of positive causal programs also extends the class of positive head-cycle-free programs, recently defined by Ben-Eliahu and Deehter. We also compare our semantics with Schaerf's approach.