Causal Graph Justifications of Logic Programs*. Issue 4 (21st July 2014)

• Record Type: Journal Article
• Authors: CABALAR, PEDRO; FANDINNO, JORGE; FINK, MICHAEL; Leuschel, Michael; Schrijvers, Tom
• Is Part Of: Theory and practice of logic programming. Volume 14:Issue 4/5(2014)
• Page Start: 603
• Page End: 618
• Publication Date: 2014-07-21
• Subjects: Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068414000234
• Languages: English
• ISSNs: 1471-0684

Abstract

<abstract abstract-type="normal"> <title>Abstract</title> <p>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 <italic>causal graphs</italic> 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 correspondence 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 operations (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 <italic>causal stable model</italic> 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 literals, something that turns out convenient for elaboration tolerance, as we explain with a running example.</p> </abstract>