Abstract
Abduction in Logic Programming started in the late 80s, early 90s, in an attempt to extend logic programming into a framework suitable for a variety of problems in Artificial Intelligence and other areas of Computer Science. This paper aims to chart out the main developments of the field over the last ten years and to take a critical view of these developments from several perspectives: logical, epistemological, computational and suitability to application. The paper attempts to expose some of the challenges and prospects for the further development of the field.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. J. Alferes, L. M. Pereira, T. Swift. Well-founded Abduction via Tabled Dual Programs. In Procs. of the 16th International Conference on Logic Programming, Las Cruces, New Mexico, Nov. 29–Dec. 4, 1999.
H. Ade and M. Denecker. Abductive inductive logic programming. In C.S. Mellish, editor, Proc. of the International Joint Conference on Artificial Intelligence, pages 1201–1209. Morgan Kaufman, 1995.
J. J. Alferes, J. A. Leite, L. M. Pereira, P. Quaresma. Planning as Abductive Updating. In D. Kitchin (ed.), Procs. of AISB’00, 2000.
Balsa, J., Dahl, V. and Pereira Lopes, J.G. Datalog Grammars for Abductive Syntactic Error Diagnosis and Repair. In Proc. Natural Language Understanding and Logic Programming Workshop, Lisbon, 1995.
M. Bruynooghe, H. Vandecasteele, D.A. de Waal, and Denecker M. Detecting unsolvable queries for definite logic programs. The Journal of Functional and Logic Programming, 1999:1–35, November 1999.
J.F. Castro, L. M. Pereira, Z. Vale. Power Grid Failure Diagnosis Certification. Technical Report, University of Lisbon.
A. Ciampolini, E. Lamma, P. Mello and P. Torroni. Expressing Collaboration and Competition Among Abductive Logic Agents. In AI*IA Notizie-Anno XIII(3), Settembre 2000, pag. 19–24.
E. Charniak and D. McDermott. Introduction to Artifical Intelligence. Addison-Wesley, 1985.
K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 293–322. Plenum Press, 1978.
L. Console, D. Theseider Dupré, and P. Torasso. On the relationship between abduction and deduction. Journal of Logic and Computation, 1(5):661–690, 1991.
L. Console, L. Portinale and Theseider Dupré, D., Using Compiled knowledge to guide and focus abductive diagnosis. IEEE Transactions on Knowledge and Data Engineering, Vol. 8(5), pp. 690–706, 1996.
L. Console, M.L. Sapino and Theseider Dupré, D. The Role of Abduction in Database View Updating. Journal of Intelligent Information Systems, Vol. 4(3), pp. 261–280, 1995.
D. de Waal, M. Denecker, M. Bruynooghe, and M. Thielscher. The generation of pre-interpretations for detecting unsolvable planning problems. In Proceedings of the Workshop on Model-Based Automated Reasoning (15th International Joint Conference on Artificial Intelligence), pages 103–112, 1997.
M. Denecker. A Terminological Interpretation of (Abductive) Logic Programming. In V.W. Marek, A. Nerode, and M. Truszczynski, editors, International Conference on Logic Programming and Nonmonotonic Reasoning, Lecture notes in Artificial Intelligence 928, pages 15–29. Springer, 1995.
M. Denecker. On the Epistemological foundations of Logic Programming and its Extensions. In AAAI Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, volume technical report SS-01-01. American Association for Artificial Intelligence, AAAI Press, 2001.
M. Denecker. Extending classical logic with inductive definitions. In J. Lloyd et al., editor, First International Conference on Computational Logic (CL2000), volume 1861 of Lecture notes in Artificial Intelligence, pages 703–717, London, July 2000. Springer.
M. Denecker and D. De Schreye. SLDNFA; an abductive procedure for normal ab-ductive programs. In K.R. Apt, editor, Proc. of the International Joint Conference and Symposium on Logic Programming, pages 686–700. MIT Press, 1992.
M. Denecker and D. De Schreye. Representing incomplete knowledge in abductive logic programming. In Proc. of the International Symposium on Logic Programming, pages 147–163. MIT Press, 1993.
M. Denecker and D. De Schreye. Representing Incomplete Knowledge in Abductive Logic Programming. Journal of Logic and Computation, 5(5):553–578, September 1995.
M. Denecker and D. De Schreye. SLDNFA: an abductive procedure for abductive logic programs. Journal of Logic Programming, 34(2):111–167, 1998.
M. Denecker, L. Missiaen, and M. Bruynooghe. Temporal reasoning with abductive event calculus. In Proc. of the European Conference on Artificial Intelligence. John Wiley and sons, 1992.
M. Denecker, K. Van Belleghem, G. Duchatelet, F. Piessens, and D. De Schreye. Using Event Calculus for Protocol Specification. An Experiment. In M. Maher, editor, The International Joint Conference and Symposium on Logic Programming, pages 170–184. MIT Press, 1996.
Marc Denecker, Maurice Bruynooghe, and Victor W Marek. Logic programming revisited: logic programs as inductive definitions. ACM Transactions on Computational Logic, 2001. accepted.
Theseider Dupré, D.. Characterizing and Mechanizing Abductive Reasoning. PhD Thesis, Dip. Informatica, Universitá di Torino, 1994.
P.M. Dung. Negations as hypotheses: an abductive foundation for Logic Programming. In Proc. of the International Conference on Logic Programming, 1991.
Thomas Eiter, Georg Gottlob, Nicola Leone. Abduction from Logic Programs: Semantics and Complexity. Theoretical Computer Science 189(1–2):129–177 (1997).
Thomas Eiter, Wolfgang Faber, Nicola Leone, and Gerald Pfeifer. Declarative problem-solving using the dlv system. In Jack Minker, editor, Logic-Based Artificial Intelligence. Kluwer Academic Publishers, 2000.
K. Eshghi. Abductive planning with Event Calculus. In R.A. Kowalski and K.A. Bowen, editors, Proc. of the International Conference on Logic Programming. The MIT press, 1988.
K. Eshghi and R.A. Kowalski. Abduction compared with negation as failure. In Proc. of the International Conference on Logic Programming. MIT-press, 1989.
D. Gabbay, L. Giordano, A. Martelli, and M.L. Sapino. Conditional reasoning in logic programming. Journal of Logic Programming, 44(1–3):37–74, 2000.
J. Gartner, T. Swift, A. Tien, C. V. Damásio, L. M. Pereira. Psychiatric Diagnosis from the Viewpoint of Computational Logic. In G. Wiggins (ed.), Procs. of AISB, 2000.
Gelfond, M., Lifschitz, V. Classical negation in logic programs and disjunctive databases. New Generation Computing, pp. 365–387, 1991.
Fages, F. A New Fixpoint Semantics for General Logic Programs Compared with the Well-Founded and the Stable Model Semantics. Proc. of ICLP’90, pp. 442–458, 1990.
P. Flach and A. C. Kakas (Eds.). Abduction and Induction: Essays on their Relation and Integration. Kluwer Academic Press, 2000.
P. Flach and A. C. Kakas. Abductive and Inductive Reasoning: Background and Issues. In Peter Flach and Antonis Kakas, editors, Abduction and Induction: essays on their relation and integration. Kluwer, 2000.
Fung, T.H. Abduction by deduction. Ph.D. Thesis, Imperial College, London, 1996.
T.H. Fung, R.A. Kowalski. The iff procedure for abductive logic programming. In Journal of Logic Programming 33(2):151–165, Elsevier, 1997.
M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. of the International Joint Conference and Symposium on Logic Programming, pages 1070–1080. IEEE, 1988.
Hobbs, J.R. An integrated abductive framework for discourse interpretation. Symposium on Automated Abduction,Stanford, 1990.
K. Inoue. Hypothetical reasoning in Logic Programs. Journal of Logic Programming, 18(3):191–228, 1994.
K. Inoue. A simple characterization of extended abduction. In: Proceedings of the First International Conference on Computational Logic, Lecture Notes in Artificial Intelligence, 1861, pages 718–732, Springer, 2000.
K. Inoue, Y. Ohta, and R. Hasegawa. Bottom-up Abduction by Model Generation. Technical Report TR-816, Institute for New Generation Computer Technology, Japan, 1993.
K. Inoue and C. Sakama. Abductive framework for nonmonotonic theory change. In: Proceedings of IJCAI-95, pages 204–210, Morgan Kaufmann, 1995.
K. Inoue and C. Sakama. Abducing priorities to derive intended conclusions. In: Proceedings of IJCAI-99, pages 44–49, Morgan Kaufmann, 1999.
K. Inoue and C. Sakama. Computing extended abduction through transaction programs. Annals of Mathematics and Artificial Intelligence, 25(3,4):339–367, 1999.
Iwayama, N. and Satoh, K. Computing Abduction by Using TMS with Top-Down Expectation. Journal of Logic Programming, Vol. 44 No. 1–3, pp. 179–206, 2000.
J.R. Josephson and S.G. Josephson, editors. Abductive Inference: Computation, Philosophy, Technology. New York: Cambridge University Press, 1994.
C.G. Jung, K. Fischer, and A. Burt. Multi-agent planning using an abductive event calculus. Technical Report DFKI Report RR-96-04, DFKI, Germany, 1996.
A. C. Kakas. ACLP: Integrating Abduction and Constraint Solving. In Proceedings of NMR2000, 2000.
Kakas, A. C., Kowalski, R. A., Toni, F., Abductive logic programming. Journal of Logic and Computation 2(6) (1993) 719–770
A. C. Kakas, R.A. Kowalski, and F. Toni. The role of abduction in logic programming. Handbook of Logic in Artificial Intelligence and Logic Programming 5, pages 235–324, D.M. Gabbay, C.J. Hogger and J.A. Robinson eds., Oxford University Press (1998)
A.C. Kakas and P. Mancarella. Generalised Stable Models: a Semantics for Abduction. In Proc. 9th European Conference on AI, ECAI90, Stockolm, 1990.
A.C. Kakas and P. Mancarella. Database updates through abduction. In Proc. of the 16th Very large Database Conference, pages 650–661. Morgan Kaufmann, 1990.
A.C. Kakas and P. Mancarella. On the relation of truth maintenance and abduction. In Proc. 1st Pacific Rim International Conference on Artificial Intelligence, PRICAI90, Nagoya, Japan, 1990.
A. C. Kakas and P. Mancarella. Knowledge assimilation and abduction. International Workshop on Truth Maintenance, Stockholm, ECAI90, Springer Verlag Lecture notes in Computer Science, Vol. 515, pp. 54–71, 1990.
Kakas, A. C., Michael, A. Integrating abductive and constraint logic programming. In Proc. International Logic Programming Conference, pp. 399–413, 1995.
A.C. Kakas and A. Michael. Air-Crew Scheduling through Abduction. Proceedings of IEA/AIE-99, pp. 600–612, 1999.
A.C. Kakas and A. Michael. An Abductive-based scheduler for air-crew assingment. Journal of Applied Artificial Intelligence Vol. 15, pp. 333–360, 2001.
A.C. Kakas, A. Michael and C. Mourlas. ACLP: a case for non-monotonic reasoning. in Proceedings of NMR98,pp. 46–56, 1998.
A.C. Kakas, A. Michael and C. Mourlas. ACLP: Abductive Constraint Logic Programming. Journal of Logic Programming (special issue on Abductive Logic Programming), Vol. 44 (1–3), pp. 129–177, 2000.
A.C. Kakas and C. Mourlas. ACLP: Flexible Solutions to Complex Problems. Proceedings of Logic Programming and Non-monotonic Reasoning, LPNMR97, 1997
A.C. Kakas and F. Riguzzi. Abductive Concept Learning. New Generation Computing, Vol. 18, pp. 243–294, 2000.
A.C Kakas, Bert Van Nuffelen, and Marc Denecker. A-system: Problem solving through abduction. In Proceedings of IJCAI’01-Seventeenth International Joint Conference on Artificial Intelligence, pp. 591–597, 2001.
R.A. Kowalski and F. Sadri, From Logic Programming towards Multi-agent Systems. Annals of Mathemathics and Artificial Intelligence, Vol 25, pp. 391–419, 1999.
R.A. Kowalski and M. Sergot. A logic-based calculus of events. New Generation Computing, 4(4):319–340, 1986.
Kowalski, R.A.; Toni, F.; Wetzel, G.; 1998. Executing suspended logic programs. Fundamenta Informaticae 34(3):203–224, ISO Press.
J. A. Leite, F. C. Pereira, A. Cardoso, L. M. Pereira. Metaphorical Mapping Consistency via Dynamic Logic Programming. In J. Lloyd et al. (eds.), Procs. of First Int. Conf. on Computational Logic (CL 2000), London, UK, pages 1362–1376, LNAI 1861, Springer, 2000.
J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.
V.W. Marek and M. Truszczyński. Stable models and an alternative logic programming paradigm. In K.R. Apt, V. Marek, M. Truszczynski, and D.S. Warren, editors, The Logic Programming Paradigm: a 25 Years Perspective, pages pp. 375–398. Springer-Verlag, 1999.
J. McCarthy. Situations, actions and causal laws. Technical Report AI-memo 1, Artifical Intelligence Program, Standford University, 1957.
Lode R. Missiaen, Marc Denecker, and Maurice Bruynooghe. CHICA, an abductive planning system based on event calculus. Journal of Logic and Computation, 5(5):579–602, September 1995.
L.R. Missiaen, M. Bruynooghe, and M. Denecker. Abductive planning with event calculus. Internal report, Department of Computer Science, K.U.Leuven, 1992.
S. Muggleton. Theory Completion in Learning. In Proceedings of Inductive Logic Programming, ILP00, 2000.
I. Niemela and P. Simons. Smodels-an implementation of the stable model and well-founded semantics for normal logic programs. Proceeings of the 4th International Conference on Logic Programming and Non-monotonic Reasoning, pp. 420–429, 1997.
I. Niemelä. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3,4):241–273, 1999.
M. Pagnucco. The role of abductive reasoning within the process of belief revision. PhD Thesis, Department of Computer Science, University of Sydney, 1996.
C.S. Peirce. Philosophical Writings of Peirce. Dover Publications, New York, 1955.
Nikolay Pelov, Emmanuel De Mot, and Marc Denecker. Logic programming approaches for representing and solving constraint satisfaction problems: a comparison. In Proceedings of LPAR’2000-7th International Conference on Logic for Programming and Automated Reasoning, 2000. accepted.
L.M. Pereira, J.N. Aparicio, and J.J. Alferes. Nonmonotonic reasoning with Well-Founded Semantics. In K. Furukawa, editor, Proc. of the eight international conference on logic programming, pages 475–489. the MIT press, 1991.
J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.
D. Poole. A Logical Framework for Default Reasoning. Artifical Intelligence, 36:27–47, 1988.
D. Poole. A methodology for using a default and abductive reasoning system. International Journal of Intelligent Systems, 5(5):521–548, December 1990.
D. Poole. Logic programming, abduction and probability: A top-down anytime algorithm for computing prior and posterior probabilities. New Generation Computing, 11(3–4):377–400, 1993.
D. Poole. Probabilistic Horn abduction and Bayesian networks. Artificial Intelligence, 64(1):81–129, 1993.
D. Poole. Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks. Artificial Intelligence, 88:69–100, 1996.
D. Poole. The independent choice logic for modelling multiple agents under uncertainty. Artificial Intelligence, 94:7–56, 1997. special issue on economic principles of multi-agent systems.
D. Poole. Probabilistic partial evaluation: Exploiting rule structure in probabilistic inference. In Proc. 15th International Joint Conf. on Artificial Intelligence (IJCAI-97), pages 1284–1291, Nagoya, Japan, 1997.
D. Poole, R. Goebel, and R. Aleliunas. Theorist: A logical reasoning system for defaults and diagnosis. In N. Cercone and G. McCalla, editors, The Knowledge Frontier: Essays in the Representation of Knowledge, pages 331–352. Springer-Verlag, New York, NY, 1987.
David Poole. Learning, bayesian probability, graphical models, and abduction. In Peter Flach and Antonis Kakas, editors, Abduction and Induction: essays on their relation and integration. Kluwer, 2000.
Poole, D., Goebel, R.G., Aleliunas, Theorist: a logical reasoning system for default and diagnosis. The Knowledge Fronteer: Essays in the Representation of Knowledge, Cercone and McCalla eds, Springer Verlag Lecture Notes in Computer Science 331–352, 1987.
D. Poole, A. Mackworth, R. G. Goebel, Computational Intelligence: a logical approach Oxford University Press, 1998.
Stathis Psillos. Ampliative Reasoning: Induction or Abduction. In ECAI96 workshop on Abductive and Inductive Reasoning, 1996.
Rochefort, S., Tarau, P. and Dahl, V. Feature Interaction Resolution Through Hypothetical Reasoning. In Proc. 4th World Multiconference on Systemics, Cybernetics and Informatics (SCI2000) and the 6th International Conference on Information Systems Analysis and Synthesis (ISAS2000), Orlando, USA July 23–26, 2000.
Saccà, D., Zaniolo, C. Stable Models and Non-Determinism in Logic Programs with Negation. Proc. of PODS’90, pp. 205–217, 1990.
F. Sadri, F. Toni, I. Xanthakos. A Logic-Agent based System for Semantic Integration. 17th International CODATA Conference-Data and Information for the Coming Knowledge Millennium-CODATA 2000, Theme I-3, Integration of Heterogeneous Databases and Data Warehousing.
F. Sadri, F. Toni. Abduction with negation as failure for active databases and agents. Proc. AI*IA 99, 6th Congress of the Italian Association for Artificial Intelligence, pages 353–362, Pitagora Editrice Bologna, 1999.
F. Sadri, F. Toni. Abduction with Negation as Failure for Active and Reactive Rules, In E. Lamma and P. Mello eds., Proc. AI*IA 99, 6th Congress of the Italian Association for Artificial Intelligence, Springer Verlag LNAI 1792, pages 49–60, 2000.
C. Sakama and K. Inoue. Representing priorities in logic programs. In: Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming, pages 82–96, MIT Press, 1996.
C. Sakama and K. Inoue. Updating extended logic programs through abduction. In: Proceedings of LPNMR’ 99, Lecture Notes in Artificial Intelligence, 1730, pages 147–161, Springer, 1999.
C. Sakama and K. Inoue. Abductive logic programming and disjunctive logic programming: their relationship and transferability. Journal of Logic Programming-Special issue on ALP 44(1–3):71–96, 2000.
C. Sakama and K. Inoue. An alternative approach to the semantics of disjunctive logic programs and deductive databases. Journal of Automated Reasoning 13(1):145–172, 1994.
F. Sadri, F. Toni and P. Torroni. Dialogues for negotiation: agent varieties and dialogue sequences. In Pre-proc. ATAL’01, special track on negotiation. Seattle, WA, August 2001.
Satoh, K. Statutory Interpretation by Case-based Reasoning through Abductive Logic Programming. Journal of Advanced Computational Intelligence, Vol. 1, No. 2, pp. 94–103, 1997.
Satoh, K. Computing Minimal Revised Logic Program by Abduction. Proc. of the International Workshop on the Principles of Software Evolution, IWPSE98, pp. 177–182, 1998.
Satoh, K. Using Two Level Abduction to Decide Similarity of Cases. Proc. of ECAI’98 pp. 398–402, 1998.
K. Satoh and N. Iwayama. A Query Evaluation method for Abductive Logic Programming. In K.R. Apt, editor, Proc. of the International Joint Conference and Symposium on Logic Programming, 1992.
Satoh, K. and Iwayama, N. Computing Abduction by Using the TMS. Proc. of ICLP’91, pp. 505–518, 1991.
Satoh, K. and Iwayama, N. A Query Evaluation Method for Abductive Logic Programming. Proc. of JICSLP’92, pp. 671–685, 1992.
Satoh, K. and Iwayama, N., “A Correct Goal-Directed Proof Procedure for a General Logic Program with Integrity Constraints”, E. Lamma and P. Mello (eds.), Extensions of Logic Programming, LNAI 660, pp. 24–44, Springer-Verlag (1993).
M. Shanahan. Prediction is deduction but explanation is abduction. In Proc. of the IJCAI89, page 1055, 1989.
F. Toni. A semantics for the Kakas-Mancarella procedure for abductive logic programming. Proc. GULP’95, M. Alpuente and M. I. Sessa, eds., pages 231–242, 1995.
F. Toni. Automated Reasoning for Collective Information Management. Proc. LocalNets, International Workshop on Community-based Interactive Systems, in conjunction with AC’99, the Annual Conference of the EC I3 Programme
K. Van Belleghem, M. Denecker, and D. De Schreye. Representing continuous change in the abductive event calculus. In Proc. of the International Conference on Logic Programming. MIT-Press, 1994.
K. Van Belleghem, M. Denecker, and D. De Schreye. The abductive event calculus as a general framework for temporal databases. In Proc. of the International Conference on Temporal Logic, pages 301–316, 1994.
K. Van Belleghem, M. Denecker, and D. De Schreye. A strong correspondence between description logics and open logic programming. In Lee Naish, editor, Proc. of the International Conference on Logic Programming, 1997, pages 346–360. MIT-press, 1997.
A. Van Gelder, K.A. Ross, and J.S. Schlipf.r The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620–650, 1991.
Bert Van Nuffelen and Marc Denecker. Problem solving in ID-logic with aggregates: some experiments. In M. Denecker, A. Kakas, and F. Toni, editors, 8th Int. Workshop on Non-Monotonic Reasoning (NMR2000), session on Abduction, pages 1–15, Breckenridge, Colorado, USA, April 9–11 2000.
B. Van Nuffelen and A.C Kakas, A-System: Programming with Abduction. In Proceedings of LPNMR2001, LNAI Vol. 2173, pp. 393–396, Springer Verlag, 2001.
Sven Verdoolaege, Marc Denecker, and Frank Van Eynde. Abductive reasoning with temporal information. In Ielka van der Sluis Harry Bunt and Elias Thijsse, editors, Proceedings of the Fourth International Workshop on Computational Semantics, pages 351–366, 2001.
Wetzel, G. Abductive and Constraint Logic Programming. Ph.D. Thesis, Imperial College, London, 1997.
G. Wetzel, F. Toni. Semantic Query Optimization through Abduction and Constraint Handling. Proc. of the International Conference on Flexible Query Answering Systems, T. Andreasen, H. L. Larsen and H. Christiansen eds., Springer Verlag LNAI 1495 (1998).
The XSB Group. The XSB logic programming system, version 2.0. 1999. Available from http://www.cs.sunysb.edu/~sbprolog.
A. Yamamoto. Using abduction for induction based on bottom up generalization. In Peter Flach and Antonis Kakas, editors, Abduction and Induction: essays on their relation and integration. Kluwer, pp. 267–280, 2000.
J.H. You, L.Y. Yuan and R. Goebel. An abductive approach to disjunctive logic programming. Journal of Logic Programming (special issue on Abductive Logic Programming), Vol. 44 (1–3), pp. 101–128, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Denecker, M., Kakas, A. (2002). Abduction in Logic Programming. In: Kakas, A.C., Sadri, F. (eds) Computational Logic: Logic Programming and Beyond. Lecture Notes in Computer Science(), vol 2407. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45628-7_16
Download citation
DOI: https://doi.org/10.1007/3-540-45628-7_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43959-2
Online ISBN: 978-3-540-45628-5
eBook Packages: Springer Book Archive