Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-17T23:46:44.470Z Has data issue: false hasContentIssue false
  • English
  • Français

The CIFF proof procedure for abductive logic programming with constraints: Theory, implementation and experiments

Published online by Cambridge University Press:  14 August 2009

PAOLO MANCARELLA ,
GIACOMO TERRENI ,
FARIBA SADRI ,
FRANCESCA TONI  and
ULLE ENDRISS
PAOLO MANCARELLA
Affiliation:
Dipartimento di Informatica, Università di Pisa, Pisa, Tuscany, Italy (e-mail: paolo.mancarella@unipi.it, terreni@di.unipi.it)
GIACOMO TERRENI
Affiliation:
Dipartimento di Informatica, Università di Pisa, Pisa, Tuscany, Italy (e-mail: paolo.mancarella@unipi.it, terreni@di.unipi.it)
FARIBA SADRI
Affiliation:
Department of Computing, Imperial College London, London, UK (e-mail: fs@doc.ic.ac.uk, ft@doc.ic.ac.uk)
FRANCESCA TONI
Affiliation:
Department of Computing, Imperial College London, London, UK (e-mail: fs@doc.ic.ac.uk, ft@doc.ic.ac.uk)
ULLE ENDRISS
Affiliation:
Institute for Logic, Language and Computation (ILLC), University of Amsterdam, Amsterdam, The Netherlands (e-mail: ulle.endriss@uva.nl)
Get access Rights & Permissions [Opens in a new window]

Abstract

We present the CIFF proof procedure for abductive logic programming with constraints, and we prove its correctness. CIFF is an extension of the IFF proof procedure for abductive logic programming, relaxing the original restrictions over variable quantification (allowedness conditions) and incorporating a constraint solver to deal with numerical constraints as in constraint logic programming. Finally, we describe the CIFF system, comparing it with state-of-the-art abductive systems and answer set solvers and showing how to use it to program some applications.

Keywords

abductionconstraintsproof procedures
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 9 , Issue 6 , November 2009 , pp. 691 - 750
Copyright
Copyright © Cambridge University Press 2009

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

Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P. and Torroni., P. 2008. Verifiable agent interaction in abductive logic programming: The SCIFF framework. ACM Transactions on Computational Logic 9 (4), 1–43.CrossRefGoogle Scholar
Alferes, J. J., Pereira, L. M. and Swift, T. 2004. Abduction in well-founded semantics and generalized stable models via tabled dual programs. Theory and Practice of Logic Programming 4, 4, 383–428.CrossRefGoogle Scholar
Aliseda-Llera, A. 1997. Abduction in Logic, Philosophy of Sand Artificial Intelligence, PhD Thesis, ILLC, University of Amsterdam, Amsterdam, The Netherlands.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York.CrossRefGoogle Scholar
Baral, C. and Gelfond, M. 1994. Logic programming and knowledge representation. Journal of Logic Programming 19/20, 73–148.CrossRefGoogle Scholar
Baselice, S., Bonatti, P. A. and Gelfond, M. 2005. Towards an integration of answer set and constraint solving. In Proceedings of the 21st International Conference on Logic Programming, Gabbrielli, M. and Gupta, G., Eds. Sitges, Spain, Lecture Notes in Computer Science, Vol. 3668, Springer, 52–66.Google Scholar
Bonatti, P. A. 2002. Abduction, ASP and open logic programs. In Proceedings of the Ninth International Workshop on Non-Monotonic Reasoning (NMR-2002), 184–190. CoRR, cs.AI/0207021, http://arxiv.org/abs/cs.AI/0207021.Google Scholar
Bressan, S., Goh, C. H., Lee, T., Madnick, S. E. and Siegel, M. 1997. A procedure for mediation of queries to sources in disparate contexts. In Proceedings of the International Logic Programming Symposium, Maluszynski, J., Ed., Port Jefferson, NY, USA, MIT Press, 213–227.Google Scholar
Christiansen, H. and Dahl, V. 2005. Hyprolog: A new logic programming language with assumptions and abduction. In Proceedings of the 21st International Conference on Logic Programming, (ICLP05), Gabbrielli, M. and Gupta, G., Eds., Sitges, Spain, Lecture Notes in Computer Science, Vol. 3668, Springer, 159–173.Google Scholar
Ciampolini, A., Lamma, E., Mello, P., Toni, F. and Torroni, P. 2003. Cooperation and competition in ALIAS: A logic framework for agents that negotiate. Annals of Mathematics and Artificial Intelligence 37, 1–2, 65–91.CrossRefGoogle Scholar
Clark, K. L. 1978. Negation as failure. In Logic and Data Bases, Gallaire, H. and Minker, J., Eds., Plenum Press, New York, 77–106.Google Scholar
Console, L., Dupre, D. T. and Torasso, P. 1991. On the relationship between abduction and deduction. Journal of Logic and Computation 1, 5, 661–690.CrossRefGoogle Scholar
D'Agostino, M., Gabbay, D. M., Hähnle, R., and Posegga, J., Eds. 1999. Handbook of Tableau Methods. Springer-Verlag.CrossRefGoogle Scholar
Denecker, M. and De Schreye, D. 1992. SLDNFA: An abductive procedure for normal abductive programs. In Proceedings of the Ninth Joint International Conference and Symposium on Logic Programming, Apt, K., Ed., Washington, DC, USA, MIT Press, 686–700.Google Scholar
Denecker, M. and De Schreye, D. 1998. SLDNFA: An abductive procedure for abductive logic programs. Journal of Logic Programming 34, 2, 111–167.CrossRefGoogle 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, Part I, Kakas, A. C. and Sadri, F., Eds., Lecture Notes in Computer Science 2407, Springer, 402–436.CrossRefGoogle Scholar
Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F. 1997. A deductive system for non-monotonic reasoning. In Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning, Dix, J., Furbach, U. and Nerode, A., Eds., Lecture Notes in Computer Science 1265, Springer, London, 364–375.Google Scholar
Endriss, U., Hatzitaskos, M., Mancarella, P., Sadri, F., Terreni, G. and Toni, F. 2005. Refinements of the CIFF procedure. In Proceedings of the 12th Workshop on Automated Reasoning, Bundy, A. and Fleuriot, J., Eds., University of Edinburgh.Google Scholar
Endriss, U., Mancarella, P., Sadri, F., Terreni, G. and Toni, F. 2004a. Abductive logic programming with CIFF: System description. In Logics in Artificial Intelligence, 9th European Conference, Alferes, J. J. and Leite, J. A., Eds., Lisbon, Portugal, Lecture Notes in Computer Science 3229, Springer, 680–684.Google Scholar
Endriss, U., Mancarella, P., Sadri, F., Terreni, G. and Toni, F. 2004b. The CIFF proof procedure for abductive logic programming with constraints. In Logics in Artificial Intelligence, 9th European Conference, Alferes, J. J. and Leite, J. A., Eds., Lisbon, Portugal, Lecture Notes in Computer Science 3229, Springer, 31–43.Google Scholar
Eshghi, K. and Kowalski, R. A. 1989. Abduction compared with negation by failure. In Proceedings of the Sixth International Conference on Logic Programming, Levi, G. and Martelli, M., Eds., Lisbon, Portugal, MIT Press, 234–254.Google Scholar
Fernández, A. J. and Hill, P. M. 2000. A comparative study of eight constraint programming languages over the Boolean and finite domains. Constraints 5, 3, 275–301.CrossRefGoogle Scholar
Frühwirth, T. W. 1998. Theory and practice of constraint handling rules. J. Log. Program. 37, 1–3, 95–138.CrossRefGoogle Scholar
Fung, T. H. 1996. Abduction by Deduction, PhD Thesis. Imperial College, University of London, London.Google Scholar
Fung, T. H. and Kowalski, R. A. 1997. The IFF proof procedure for abductive logic programming. Journal of Logic Programming 33, 2, 151–165.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the Fifth International Conference and Symposium on Logic Programming (ICLP/SLP), Kowalski, R. A. and Bowen, K., Eds., Seattle, Washington, USA, MIT Press, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.CrossRefGoogle Scholar
Holzbaur, C. 1992. Metastructures versus attributed variables in the context of extensible unification. In Proceedings of Fourth Symposium on Programming Language Implementation and Logic Programming, Bruynooghe, M. and Wirsing, M., Eds., Leuven, Belgium, Lecture Notes in Computer Science 631, Springer, 260–268.CrossRefGoogle Scholar
Jaffar, J. and Maher, M. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Jaffar, J., Maher, M. J., Marriott, K. and Stuckey, P. J. 1998. The semantics of constraint logic programs. Journal of Logic Programming 37, 1–3, 1–46.CrossRefGoogle Scholar
Kakas, A., Kowalski, R. and Toni, F. 1998. The role of abduction in logic programming. In Handbook of Logic in Artificial Intelligence and Logic Programming 5. Oxford University Press, 235–324.Google Scholar
Kakas, A. C., Kowalski, R. A. and Toni, F. 1992. Abductive logic programming. Journal of Logic and Computation 2, 6, 719–770.CrossRefGoogle Scholar
Kakas, A. C. and Mancarella, P. 1990a. Abductive logic programming. In Proceedings of the Workshop Logic Programming and Non-Monotonic Logic, Marek, V. W., Nerode, A., Pedreschi, D. and Subrahmanian, V. S., Eds., Austin, TX, USA, 49–61.Google Scholar
Kakas, A. C. and Mancarella, P. 1990b. Generalized stable models: A semantics for abduction. In Proceedings of the Ninth European Conference on Artificial Intelligence, Stockholm, Sweden, 385–391.Google Scholar
Kakas, A. C., Mancarella, P., Sadri, F., Stathis, K. and Toni, F. 2004. The KGP model of agency. In Proceedings of the 16th European Conference on Artificial Intelligence, López de Mántaras, R., Saitta, L., Eds., Valencia, Spain, IOS Press, 33–37.Google Scholar
Kakas, A. C., Mancarella, P., Sadri, F., Stathis, K. and Toni, F. 2008. Computational logic foundations of KGP agents. Journal of Artificial Intelligence Research 33, 285–348.CrossRefGoogle Scholar
Kakas, A. C., Michael, A. and Mourlas, C. 2000. ACLP: Abductive constraint logic programming. Journal of Logic Programming 44, 129–177.CrossRefGoogle Scholar
Kakas, A. C., Van Nuffelen, B. and Denecker, M. 2001. A-system: Problem solving through abduction. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, Nebel, B., Ed., Seattle, Washington, USA, Morgan Kaufmann, 591–596.Google Scholar
Klarman, S. 2008. ABox Abduction in Description Logic, MS Thesis. ILLC, University of Amsterdam, Amsterdam, The Netherlands.Google Scholar
Kowalski, R. and Sergot, M. 1986. A logic-based calculus of events. New Generation Computing 4, 1, 67–95.CrossRefGoogle Scholar
Kowalski, R. A., Toni, F. and Wetzel, G. 1998. Executing suspended logic programs. Fundamenta Informaticae 34, 3, 203–224.CrossRefGoogle Scholar
Kunen, K. 1987. Negation in logic programming. Journal of Logic Programming 4, 4, 289–308.CrossRefGoogle Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.CrossRefGoogle Scholar
Lin, F. and You, J.-H. 2002. Abduction in logic programming: A new definition and an abductive procedure based on rewriting. Artificial Intelligence 140, 1/2, 175–205.CrossRefGoogle Scholar
Lloyd, J. W. 1987. Foundations of Logic Programming, 2nd extended ed. Springer-Verlag, New York.CrossRefGoogle Scholar
Mancarella, P., Sadri, F., Terreni, G. and Toni, F. 2004. Planning partially for situated agents. In Proceedings of the Fifth International Workshop on Computational Logic in Multi-Agent Systems, Leite, J. A. and Torroni, P., Eds., Lisbon, Portugal, Lecture Notes in Computer Science 3487, Springer, 230–248.Google Scholar
Mancarella, P., Sadri, F., Terreni, G. and Toni, F. 2007. Programming applications in CIFF. In Proceedings of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning, Baral, C., Brewka, G. and Schlipf, J. S., Eds., Tempe, AZ, USA, Lecture Notes in Computer Science 4483, Springer, 284–289.CrossRefGoogle Scholar
Mancarella, P., Terreni, G. and Toni, F. 2007. Web sites verification: An abductive logic programming tool. In Proceedings of the 23rd International Conference on Logic Programming, Dahl, V. and Niemelä, I., Eds., Porto, Portugal, Lecture Notes in Computer Science 4670, Springer, 434–435.Google Scholar
Mancarella, P., Terreni, G. and Toni, F. 2009. Web sites repairing through abduction. Electronic Notes on Theoretical Computer Science 235, 137–152.CrossRefGoogle Scholar
Marek, W. and Truszczynski, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective. Springer-Verlag, 375–398.CrossRefGoogle Scholar
Martelli, A. and Montanari, U. 1982. An efficient unification algorithm. ACM Transactions on Programming Languages and Systems 4, 2, 258–282.CrossRefGoogle Scholar
Mayer, M. C. and Pirri, F. 1993. First order abduction via tableau and sequent calculi. Bulletin of the IGPL 1, 1, 99–117.CrossRefGoogle Scholar
Mellarkod, V. S. and Gelfond, M. 2008. Integrating answer set reasoning with constraint solving techniques. In Proceedings of the 9th International Symposium on Functional and Logic Programming, Garrigue, J. and Hermenegildo, M. V., Eds., Ise, Japan, Lecture Notes in Computer Science 4989, Springer, 15–31.CrossRefGoogle Scholar
Miller, R. and Shanahan, M. 2002. Some alternative formulations of the event calculus. In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, Kakas, A. C. and Sadri, F., Eds., Lecture Notes in Computer Science 2408, Springer, London, 452–490.CrossRefGoogle Scholar
Niemela, I. and Simons, P. 1997. SMODELS – an implementation of the stable model and well-founded semantics for normal logic programs. In Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning, Dix, J., Furbach, U. and Nerode, A., Eds., London, UK, Lecture Notes in Computer Science 1265, Springer, 421–430.Google Scholar
Pereira, L. M., Aparício, J. N. and Alferes, J. J. 1991. Nonmonotonic reasoning with well founded semantics. In Proceedings of the Eighth International Conference on Logic Programming, Furukawa, K., Ed., Paris, France, MIT Press, 475–489.Google Scholar
Sadri, F. and Toni, F. 1999. Abduction with negation as failure for active and reactive rules. In AI*IA 99: Advances in Artificial Intelligence, Sixth Congress of the Italian Association for Artificial Intelligence, Lamma, E. and Mello, P., Eds., Bologna, Italy, Lecture Notes in Computer Science 1792, Springer, 49–60.Google Scholar
Sadri, F., Toni, F. and Torroni, P. 2002. An abductive logic programming architecture for negotiating agents. In Logics in Artificial Intelligence, European Conference, Flesca, S., Greco, S., Leone, N. and Ianni, G., Eds., Cosenza, Italy, Lecture Notes in Computer Science 2424, Springer, 419–431.Google Scholar
Shanahan, M. 1989. Prediction is deduction but explanation is abduction. In Proceedings of the 11th International Joint Conference on Artificial Intelligence, Sridharan, N. S., Ed., Detroit, MI, USA, Morgan Kaufmann, 1055–1060.Google Scholar
Simons, P. 2000. Extending and Implementing the Stable Model Semantics, Technical Report. Helsinki University of Technology, Espoo, Helsinki, Finland.Google Scholar
SOCS-Consortium. 2002–2005. Societies of computees (SOCS): A computational logic model for the description, analysis and verification of global and open societies of heterogeneous computees. IST-2001-32530 [online]. Accessed 22 July 2009. URL: http://lia.deis.unibo.it/Research/SOCS/Google Scholar
Terreni, G. 2008a. The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Definition, Implementation and a Web Application, PhD Thesis. Università di Pisa, Pisa, Tuscany, Italy.Google Scholar
Terreni, G. 2008b. The CIFF system [online]. Accessed 22 July 2009. URL: http://www.di.unipi.it/~terreni/research.phpGoogle Scholar
Toni, F. 2001. Automated information management via abductive logic agents. Telematics and Informatics 18, 1, 89–104e.CrossRefGoogle Scholar
Van Gelder, A., Ross, K., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620–650.CrossRefGoogle Scholar
Van Nuffelen, B. 2004. Abductive Constraint Logic Programming: Implementation and Applications, PhD Thesis. K. U. Leuven, Leuven, Belgium.Google Scholar
Wetzel, G., Kowalski, R. A., and Toni, F. 1996. PROCALOG – programming with constraints and abducibles in logic (poster abstract). In Proceedings of the 13th Joint International Conference and Symposium on Logic Programming, Maher, M. J., Ed., Bonn, Germany, MIT Press, 535.Google Scholar
Wielemaker, J. 2003. An overview of the SWI-Prolog programming environment. In Proceedings of the 13th International Workshop on Logic Programming Environments, Mesnard, F. and Serebrenik, A., Eds., Mumbai, India, Report CW371 Katholieke Universiteit Leuven, Department of Computer Science, 1–16. Accessed 22 July 2009. URL: http://www.swi-prolog.org/.Google Scholar