Causal Graph Justifications of Logic Programs
This work addresses the need for semantic justifications in logic programming, offering a method to derive causal information algebraically, which is incremental as it builds on existing stable models semantics.
The authors tackled the problem of associating justifications with true atoms in logic programs under stable models semantics by introducing a multi-valued extension where justifications are expressed as causal graphs. They showed that for positive programs, these causal justifications correspond to syntactic proofs, and extended this to programs with negation by defining causal stable models, with default negation treated as 'absence of proof'.
In this work we propose a multi-valued extension of logic programs under the stable models semantics where each true atom in a model is associated with a set of justifications. These justifications are expressed in terms of causal graphs formed by rule labels and edges that represent their application ordering. For positive programs, we show that the causal justifications obtained for a given atom have a direct correspon- dence to (relevant) syntactic proofs of that atom using the program rules involved in the graphs. The most interesting contribution is that this causal information is obtained in a purely semantic way, by algebraic op- erations (product, sum and application) on a lattice of causal values whose ordering relation expresses when a justification is stronger than another. Finally, for programs with negation, we define the concept of causal stable model by introducing an analogous transformation to Gelfond and Lifschitz's program reduct. As a result, default negation behaves as "absence of proof" and no justification is derived from negative liter