Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T23:16:26.300Z Has data issue: false hasContentIssue false

Causal Graph Justifications of Logic Programs*

Published online by Cambridge University Press:  21 July 2014

PEDRO CABALAR
Affiliation:
Department of Computer Science, University of Corunna, Spain (e-mail: cabalar@udc.es, jorge.fandino@udc.es)
JORGE FANDINNO
Affiliation:
Department of Computer Science, University of Corunna, Spain (e-mail: cabalar@udc.es, jorge.fandino@udc.es)
MICHAEL FINK
Affiliation:
Vienna University of Technology, Institute for Information Systems, Vienna, Austria (e-mail: fink@kr.tuwien.ac.at)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 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 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 literals, something that turns out convenient for elaboration tolerance, as we explain with a running example.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2014 
Supplementary material: PDF

CABALAR et al.

Causal Graph Justifications of Logic Programs

Download CABALAR et al.(PDF)
PDF 158.8 KB