Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T07:55:56.327Z Has data issue: false hasContentIssue false
  • English
  • Français

Causal Graph Justifications of Logic Programs*

Published online by Cambridge University Press:  21 July 2014

PEDRO CABALAR ,
JORGE FANDINNO  and
MICHAEL FINK
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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Answer Set ProgrammingCausalityKnowledge RepresentationMulti-valued Logic Programming
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 603 - 618
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This research was partially supported by Spanish MEC project TIN2009-14562-C05-04, Xunta projects GPC2013/070 and INCITE 2011, Inditex-University of Corunna 2013 grants and the Austrian Science Fund (FWF) project P24090.

References

Artëmov, S. N. 2001. Explicit provability and constructive semantics. Bulletin of Symbolic Logic 7, 1, 1–36.Google Scholar
Brewka, G., Eiter, T., and Truszczynski, M. 2011. Answer set programming at a glance. Commun. ACM 54, 12, 92–103.Google Scholar
Broda, K., Gabbay, D., Lamb, L. and Russo, A. 2004. Compiled Labelled Deductive Systems: A Uniform Presentation of Non-Classical Logics. Research Studies Press.Google Scholar
Cabalar, P. 2011. Logic programs and causal proofs. In AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning. AAAI.Google Scholar
Cabalar, P. and Fandinno, J. 2013. An algebra of causal chains. In Proc. of the 6th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP'13).Google Scholar
Damásio, C. V., Analyti, A., and Antoniou, G. 2013. Justifications for logic programming. In Proc. of the 12th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning, (LPNMR'13). Lecture Notes in Computer Science, vol. 8148. Springer, 530–542.CrossRefGoogle Scholar
Denecker, M. and De Schreye, D. 1993. Justification semantics: A unifiying framework for the semantics of logic programs. In Proc. of the Logic Programming and Nonmonotonic Reasoning Workshop. 365–379.Google Scholar
Fages, F. 1991. A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics. New Generation Computing 9, 3–4, 425–443.CrossRefGoogle Scholar
Gebser, M., Pührer, J., Schaub, T., and Tompits, H. 2008. Meta-programming technique for debugging answer-set programs. In Proc. of the 23rd Conf. on Artificial Inteligence (AAAI'08). 448–453.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proc. of the Fifth International Conference and Symposium (Volume 2), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Cambridge, MA, 1070–1080.Google Scholar
Hall, N. 2004. Two concepts of causality. 181–276.Google Scholar
Halpern, J. Y. 2008. Defaults and normality in causal structures. In Proc. of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008). 198–208.Google Scholar
Halpern, J. Y. and Pearl, J. 2005. Causes and explanations: A structural-model approach. part I: Causes. British Journal for Philosophy of Science 56, 4, 843–887.Google Scholar
Hitchcock, C. and Knobe, J. 2009. Cause and norm. Journal of Philosophy 11, 587–612.Google Scholar
Hume, D. 1748. An enquiry concerning human understanding. Reprinted by Open Court Press, LaSalle, IL, 1958.Google Scholar
Kifer, M. and Subrahmanian, V. S. 1992. Theory of generalized annotated logic programming and its applications. Journal of Logic Programming 12.Google Scholar
Liang, S. and Kifer, M. 2013. A practical analysis of non-termination in large logic programs. TPLP 13, 4–5, 705–719.Google Scholar
Lin, F. 1995. Embracing causality in specifying the indirect effects of actions. In Proc. of the Intl. Joint Conf. on Artificial Intelligence (IJCAI), Mellish, C. S., Ed. Morgan Kaufmann, Montreal, Canada.Google Scholar
McCain, N. and Turner, H. 1997. Causal theories of action and change. In Proc. of the AAAI-97. 460–465.Google Scholar
McCarthy, J. 1977. Epistemological problems of Artificial Intelligence. In Proc. of the Intl. Joint Conf. on Artificial Intelligence (IJCAI). MIT Press, Cambridge, MA, 1038–1044.Google Scholar
McCarthy, J. 1998. Elaboration tolerance. In Proc. of the 4th Symposium on Logical Formalizations of Commonsense Reasoning (Common Sense 98). London, UK, 198–217. Updated version at http://www-formal.stanford.edu/jmc/elaboration.ps.Google Scholar
Pearce, D. 2006. Equilibrium logic. Ann. Math. Artif. Intell. 47, 1-2, 3–41.Google Scholar
Pearl, J. 2000. Causality: models, reasoning, and inference. Cambridge University Press, New York, NY, USA.Google Scholar
Pereira, L. M., Aparício, J. N., and Alferes, J. J. 1991. Derivation procedures for extended stable models. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, Mylopoulos, J. and Reiter, R., Eds. Morgan Kaufmann, 863–869.Google Scholar
Pontelli, E., Son, T. C., and El-Khatib, O. 2009. Justifications for logic programs under answer set semantics. Theory and Practice of Logic Programming 9, 1, 1–56.Google Scholar
Schulz, C., Sergot, M., and Toni, F. 2013. Argumentation-based answer set justification. In Proc. of the 11th Intl. Symposium on Logical Formalizations of Commonsense Reasoning (Commonsense'13).Google Scholar
Stumme, G. 1997. Free distributive completions of partial complete lattices. Order 14, 179–189.CrossRefGoogle Scholar
Thielscher, M. 1997. Ramification and causality. Artificial Intelligence Journal 89, 1–2, 317–364.Google Scholar
van Emden, M. H. and Kowalski, R. A. 1976. The semantics of predicate logic as a programming language. J. ACM 23, 4, 733–742.Google Scholar
Vennekens, J. 2011. Actual causation in cp-logic. TPLP 11, 4–5, 647–662.Google Scholar
Supplementary material: PDF

CABALAR et al.

Causal Graph Justifications of Logic Programs

Download CABALAR et al.(PDF)
PDF 158.8 KB