Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T11:17:50.589Z Has data issue: false hasContentIssue false
  • English
  • Français

Enablers and inhibitors in causal justifications of logic programs*

Published online by Cambridge University Press:  03 May 2016

PEDRO CABALAR  and
JORGE FANDINNO
PEDRO CABALAR
Affiliation:
Department of Computer Science, University of Corunna, A Corunna, Spain (e-mail: [email protected], [email protected])
JORGE FANDINNO
Affiliation:
Department of Computer Science, University of Corunna, A Corunna, Spain (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we propose an extension of logic programming where each default literal derived from the well-founded model is associated to a justification represented as an algebraic expression. This expression contains both causal explanations (in the form of proof graphs built with rule labels) and terms under the scope of negation that stand for conditions that enable or disable the application of causal rules. Using some examples, we discuss how these new conditions, we respectively call enablers and inhibitors, are intimately related to default negation and have an essentially different nature from regular cause-effect relations. The most important result is a formal comparison to the recent algebraic approaches for justifications in logic programming: Why-not Provenance and Causal Graphs. We show that the current approach extends both Why-not Provenance and Causal Graphs justifications under the well-founded semantics and, as a byproduct, we also establish a formal relation between these two approaches.

Keywords

causal justificationswell-founded semanticsstable modelsanswer set programming
Type
Rapid Communication
Information
Theory and Practice of Logic Programming , Volume 17 , Issue 1 , January 2017 , pp. 49 - 74
Copyright
Copyright © Cambridge University Press 2016 

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 is an extended version of a paper presented at the Logic Programming and Non-monotonic Reasoning Conference (LPNMR 2015), invited as a rapid communication in TPLP. The authors acknowledge the assistance of the conference program chairs Giovambattista Ianni and Miroslaw Truszczynski.

References

Cabalar, P., Fandinno, J. and Fink, M. 2014a. Causal graph justifications of logic programs. Theory and Practice of Logic Programming TPLP 14, 4–5, 603–618. Cambridge University Press, Cambridge, United Kingdom.CrossRefGoogle Scholar
Cabalar, P., Fandinno, J. and Fink, M. 2014b. A complexity assessment for queries involving sufficient and necessary causes. In Proc. Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24–26, 2014, Fermé, E. and Leite, J., Eds. Lecture Notes in Computer Science, vol. 8761. Springer, Berlin, Germany, 297–310.Google Scholar
Damásio, C. V., Analyti, A. and Antoniou, G. 2013. Justifications for logic programming. In Proc. Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15–19, 2013, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, Berlin, Germany, 530–542.Google Scholar
Denecker, M. and Schreye, D. D. 1993. Justification semantics: A unifiying framework for the semantics of logic programs. In Proc. Logic Programming and Non-monotonic Reasoning, 2nd International Workshop, LPNMR 1993, Lisbon, Portugal, June 1993. The MIT Press, Cambridge, Massachusetts, United States, 365–379.Google Scholar
Fandinno, J. 2015a. A causal semantics for logic programming. Ph.D. thesis, University of Corunna, A Corunna, Spain.Google Scholar
Fandinno, J. 2015b. Towards deriving conclusions from cause-effect relations. In Proc. of the 8th International Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2015, Cork, Ireland, August 31, 2015.Google Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2007. A new perspective on stable models. In Proc. of the 20th International Joint Conference on Artificial Intelligence, IJCAI 2007, Hyderabad, India, January 6–12, 2007, Veloso, M. M., Ed. AAAI Press, Menlo Park, California, United States, 372–379.Google Scholar
Gebser, M., Pührer, J., Schaub, T. and Tompits, H. 2008. A meta-programming technique for debugging answer-set programs. In Proc. of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13–17, 2008, Fox, D. and Gomes, C. P., Eds. AAAI Press, Menlo Park, California, United States, 448–453.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the 5th International Conference and Symposium, Seattle, Washington, August 15–19, Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Cambridge, Massachusetts, United States, 1070–1080.Google Scholar
Hall, N. 2000. Causation and the price of transitivity. The Journal of Philosophy 97, 4, 198–222. The Journal of Philosophy, Inc, New York, New York, United States.CrossRefGoogle Scholar
Hall, N. 2004. Two concepts of causation. In Causation and Counterfactuals, Collins, J., Hall, N., and Paul, L. A., Eds. Cambridge, MA: MIT Press, Cambridge, Massachusetts, United States, 225–276.Google Scholar
Hall, N. 2007. Structural equations and causation. Philosophical Studies 132, 1, 109–136.Google Scholar
Halpern, J. Y. 2008. Defaults and normality in causal structures. In Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference, KR 2008, Sydney, Australia, September 16–19, 2008, Brewka, G. and Lang, J., Eds. AAAI Press, Menlo Park, California, United States, 198–208.Google Scholar
Halpern, J. Y. 2014. Appropriate causal models and stability of causation. In Principles of Knowledge Representation and Reasoning: Proceedings of the 14th International Conference, KR 2014, Vienna, Austria, July 20–24, 2014, Baral, C., Giacomo, G. D., and Eiter, T., Eds. AAAI Press, Menlo Park, California, United States.Google Scholar
Halpern, J. Y. 2015. A modification of the halpern-pearl definition of causality. In Proc. of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25–31, 2015, Yang, Q. and Wooldridge, M., Eds. AAAI Press, Menlo Park, California, United States, 3022–3033.Google Scholar
Halpern, J. Y. and Hitchcock, C. 2011. Actual causation and the art of modeling. CoRR abs/1106.2652, 2015.Google Scholar
Halpern, J. Y. and Pearl, J. 2001. Causes and explanations: A structural-model approach. Part I: Causes. In Proc. of the 17th Conference in Uncertainty in Artificial Intelligence, UAI 2001, University of Washington, Seattle, Washington, USA, August 2–5, Morgan Kaufmann, San Francisco, CA, 194–202.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. Oxford University Press, Oxford, United Kingdom.CrossRefGoogle Scholar
Hanks, S. and McDermott, D. V. 1987. Nonmonotonic logic and temporal projection. Artificial Intelligence 33, 3, 379–412. Philadelphia, Pennsylvania, United States.CrossRefGoogle Scholar
Hitchcock, C. and Knobe, J. 2009. Cause and norm. Journal of Philosophy 11, 587–612. The Journal of Philosophy, Inc, New York, New York, United States.Google Scholar
Hume, D. 1748. An enquiry concerning human understanding. Reprinted by Open Court Press, LaSalle, IL, 1958.Google Scholar
Lewis, D. K. 2000. Causation as influence. The Journal of Philosophy 97, 4, 182–197. The Journal of Philosophy, Inc, New York, New York, United States.Google Scholar
Lin, F. 1995. Embracing causality in specifying the indirect effects of actions. In Proc. of the 14th International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20–25 1995, 2 Volumes. Morgan Kaufmann, San Francisco, CA, 1985–1993.Google Scholar
Marek, V. W. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm, Apt, K. R., Marek, V. W., Truszczyński, M., and Warren, D., Eds. Artificial Intelligence. Springer, Berlin, Germany, 375–398.Google Scholar
Maudlin, T. 2004. Causation, counterfactuals, and the third factor. In Causation and Counterfactuals, Collins, J., Hall, E. J., and Paul, L. A., Eds. MIT Press, Cambridge, Massachusetts, United States, 419–443 Google Scholar
McCain, N. and Turner, H. 1997. Causal theories of action and change. In Proc. of the 14th National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27–31, 1997, Providence, Rhode Island, Kuipers, B. and Webber, B. L., Eds. AAAI Press/MIT Press, Menlo Park/Cambridge, California/Massachusetts, United States, 460–465.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273. Springer, Berlin, Germany.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2010. Catching the ouroboros: On debugging non-ground answer-set programs. In Proc. CoRR abs/1007.4986, 2010.Google Scholar
Pearce, D. 1996. A new logical characterisation of stable models and answer sets. In Non-Monotonic Extensions of Logic Programming, NMELP 1996, Bad Honnef, Germany, September 5–6, 1996, Selected Papers, Dix, J., Pereira, L. M., and Przymusinski, T. C., Eds. Lecture Notes in Computer Science, vol. 1216. Springer, Berlin, Germany, 57–70.Google Scholar
Pearl, J. 2000. Causality: models, reasoning, and inference. Cambridge University Press, New York, NY, USA.Google Scholar
Pemmasani, G., Guo, H., Dong, Y., Ramakrishnan, C. R. and Ramakrishnan, I. V. 2004. Online justification for tabled logic programs. In Proc. Functional and Logic Programming, 7th International Symposium, FLOPS 2004, Nara, Japan, April 7–9, 2004, Kameyama, Y. and Stuckey, P. J., Eds. Lecture Notes in Computer Science, vol. 2998. Springer, Berlin, Germany, 24–38.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 TPLP 9, 1, 1–56. Cambridge University Press, Cambridge, United Kingdom.Google Scholar
Schulz, C. and Toni, F. 2016. Justifying answer sets using argumentation. In Theory and Practice of Logic Programming TPLP 16, 1, 59–110. Cambridge University Press, Cambridge, United Kingdom.Google Scholar
Specht, G. 1993. Generating explanation trees even for negations in deductive database systems. In Proc. of the 15th Workshop on Logic Programming Environments (LPE 1993), October 29-30, 1993, In conjunction with ILPS 1993, Vancouver, British Columbia, Canada, Ducassé, M., Charlier, B. L., Lin, Y., and Yalçinalp, L. Ü., Eds. IRISA, Campus de Beaulieu, France, 8–13.Google Scholar
Thielscher, M. 1997. Ramification and causality. Artificial Intelligence 89, 1–2, 317–364. Morgan Kaufmann, San Francisco, CA.Google Scholar
Van Gelder, A. 1989. The alternating fixpoint of logic programs with negation. In Proc. of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29–31, 1989, Philadelphia, Pennsylvania, USA, Silberschatz, A., Ed. ACM Press, Inc, New York, New York, United States, 1–10.Google Scholar
Van Gelder, A., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM (JACM) 38, 3, 620–650. ACM Press, Inc, New York, New York, United States.Google Scholar
Supplementary material: PDF

Cabalar and Fandinno supplementary material

Online Appendix

Download Cabalar and Fandinno supplementary material(PDF)
PDF 213.2 KB