Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-25T05:36:27.459Z Has data issue: false hasContentIssue false
  • English
  • Français

A Measure of Arbitrariness in Abductive Explanations

Published online by Cambridge University Press:  21 July 2014

LUCIANO CAROPRESE ,
IRINA TRUBITSYNA ,
Mirosław Truszczyński  and
Ester Zumpano
LUCIANO CAROPRESE
Affiliation:
DIMES, Università della Calabria, Cosenza, Italy (e-mail: [email protected], [email protected])
IRINA TRUBITSYNA
Affiliation:
DIMES, Università della Calabria, Cosenza, Italy (e-mail: [email protected], [email protected])
Mirosław Truszczyński
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, USA (e-mail: [email protected])
Ester Zumpano
Affiliation:
DIMES, Università della Calabria, Cosenza, Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the framework of abductive logic programming extended with integrity constraints. For this framework, we introduce a new measure of the simplicity of an explanation based on its degree of arbitrariness: the more arbitrary the explanation, the less appealing it is, with explanations having no arbitrariness — they are called constrained — being the preferred ones. In the paper, we study basic properties of constrained explanations. For the case when programs in abductive theories are stratified we establish results providing a detailed picture of the complexity of the problem to decide whether constrained explanations exist.

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. 665 - 679
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.)

References

Balsa, J., Dahl, V., and Lopes, J. G. P. 1995. Datalog Grammars for Abductive Syntactic Error Diagnosis and Repair. In Proceedings of the Natural Language Understanding and Logic Programming Workshop, Lisbon, 1995. 111–125.Google Scholar
Baral, C. and Gelfond, M. 1994. Logic Programming and Knowledge Representation. J. Log. Program. 19/20, 73–148.Google Scholar
Bylander, T., Allemang, D., Tanner, M. C., and Josephson, J. R. 1991. The Computational Complexity of Abduction. Artificial Intelligence 49, 1–3, 25–60.Google Scholar
Caroprese, L., Trubitsyna, I., Truszczynski, M., and Zumpano, E. 2012. The View-update Problem for Indefinite Databases. In Proceedings of the 13th European Conference on Logics in Artificial Intelligence, JELIA 2012, del Cerro, L. F., Herzig, A., and Mengin, J., Eds. Lecture Notes in Computer Science, vol. 7519. Springer, 134–146.Google Scholar
Console, L., Portinale, L., and Dupré, D. T. 1996. Using Compiled Knowledge to Guide and Focus Abductive Diagnosis. IEEE Trans. Knowl. Data Eng. 8, 5, 690–706.Google Scholar
Console, L., Sapino, M. L., and Dupré, D. T. 1995. The Role of Abduction in Database View Updating. J. Intell. Inf. Syst. 4, 3 (May), 261–280.Google Scholar
Denecker, M. and Kakas, A. C. 2002. Abduction in Logic Programming. In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Kakas, A. C. and Sadri, F., Eds. Lecture Notes in Computer Science, vol. 2407. Springer, 402–436.Google Scholar
Denecker, M. and Schreye, D. D. 1995. Representing Incomplete Knowledge in Abductive Logic Programming. J. Log. Comput. 5, 5, 553–577.Google Scholar
do Lago Pereira, S. and de Barros, L. N. 2004. Planning with Abduction: A Logical Framework to Explore Extensions to Classical Planning. In Proceedings of the 17th Brazilian Symposium on Artificial Intelligence, SBIA 2004, Bazzan, A. L. C. and Labidi, S., Eds. Lecture Notes in Computer Science, vol. 3171. Springer, 62–72.CrossRefGoogle Scholar
Dung, P. M. 1991. Negations as Hypotheses: An Abductive Foundation for Logic Programming. In Proceedings of the 8th International Conference on Logic Programming, Furukawa, K., Ed. MIT Press, 3–17.Google Scholar
Eiter, T., Gottlob, G., and Leone, N. 1997. Abduction from Logic Programs: Semantics and Complexity. Theor. Comput. Sci. 189, 1-2, 129–177.Google Scholar
Eshghi, K. 1988. Abductive Planning with Event Calculus. In Proceedings of the 5th International Conference and Symposium on Logic Programming, Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, 562–579.Google Scholar
Eshghi, K. and Kowalski, R. A. 1989. Abduction Compared with Negation by Failure. In Proceedings of the 6th International Conference on Logic Programming, Levi, G. and Martelli, M., Eds. MIT Press, 234–254.Google Scholar
Fraternali, P. and Paraboschi, S. 1993. A Review of Repairing Techniques for Integrity Maintenance. In Proceedings of the 1st International Workshop on Rules in Database Systems, Paton, N. W. and Williams, M. H., Eds. Workshops in Computing. Springer, 333–346.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The Stable Semantics for Logic Programs. In Proceedings of the 5th International Conference and Symposium on Logic Programming, Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, 1070–1080.Google Scholar
Inoue, K. and Sakama, C. 1995. Abductive Framework for Nonmonotonic Theory Change. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 95. Morgan Kaufmann, 204–210.Google Scholar
Josephson, J. and Josephson, S. 1996. Abductive Inference: Computation, Philosophy, Technology. Cambridge University Press.Google Scholar
Kakas, A. C., Kowalski, R. A., and Toni, F. 1992. Abductive Logic Programming. J. Log. Comput. 2, 6, 719–770.Google Scholar
Kakas, A. C. and Mancarella, P. 1990a. Database updates through abduction. In Proceedings of the 16th International Conference on Very Large Data Bases, VLDB 1990, McLeod, D., Sacks-Davis, R., and Schek, H.-J., Eds. Morgan Kaufmann, 650–661.Google Scholar
Kakas, A. C. and Mancarella, P. 1990b. Generalized stable models: A semantics for abduction. In Proceedings of the 9th European Conference on Artificial Intelligence, ECAI 1990, Aiello, L., Ed. Pitman, London/Boston, 385–391.Google Scholar
Konolige, K. 1992. Abduction Versus Closure in Causal Theories. Artificial Intelligence 53, 2–3, 255–272.Google Scholar
Maher, M. J. 2005. Herbrand constraint abduction. In Proceedings of the 20th IEEE Symposium on Logic in Computer Science, LICS 2005. IEEE Computer Society, 397–406.Google Scholar
Marek, W. and Subrahmanian, V. 1992. The Relationship Between Stable, Supported, Default and Autoepistemic Semantics for General Logic Programs. Theoretical Computer Science 103, 2, 365–386.Google Scholar
Mayol, E. and Teniente, E. 1999. A Survey of Current Methods for Integrity Constraint Maintenance and View Updating. In Advances in Conceptual Modeling, Proceedings of ER '99 Workshops on Evolution and Change in Data Management, Reverse Engineering in Information Systems, and the World Wide Web and Conceptual Modeling, Chen, P. P., Embley, D. W., Kouloumdjian, J., Liddle, S. W., and Roddick, J. F., Eds. Lecture Notes in Computer Science, vol. 1727. Springer, 62–73.Google Scholar
Peirce, C. 1995. Abduction and Induction. In Philosophical Writing of Peirce, Buchler, J., Ed. Dover, New York, Chapter 11.Google Scholar
Peng, Y. and Reggia, J. 1990. Abductive Inference Models for Diagnostic Problem Solving. Springer.Google Scholar
Pople, H. E. 1973. On the Mechanization of Abductive Logic. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence, IJCAI 1973, Nilsson, N. J., Ed. William Kaufmann, 147–152.Google Scholar
Satoh, K. 1996. Translating Case-Based Reasoning into Abductive Logic Programming. In Proceedings of the 12th European Conference on Artificial Intelligence, ECAI 1996, Wahlster, W., Ed. John Wiley and Sons, Chichester, UK, 142–146.Google Scholar
Selman, B. and Levesque, H. J. 1990. Abductive and Default Reasoning: A Computational Core. In Proceedings of the 8th National Conference on Artificial Intelligence, AAAI 1990, Shrobe, H. E., Dietterich, T. G., and Swartout, W. R., Eds. 343–348.Google Scholar
Van Gelder, A., Ross, K., and Schlipf, J. 1991. The Well-Founded Semantics for General Logic Programs. Journal of the ACM 38, 3, 620–650.Google Scholar
Supplementary material: PDF

CAROPRESE et al.

A Measure of Arbitrariness in Abductive Explanations

Download CAROPRESE et al.(PDF)
PDF 73.8 KB