×

Executable specifications for hypothesis-based reasoning with Prolog and Constraint Handling Rules. (English) Zbl 1176.68158

Summary: Constraint Handling Rules (CHR) is an extension to Prolog which opens up a spectrum of hypothesis-based reasoning in logic programs without additional interpretation overhead. Abduction with integrity constraints is one example of hypothesis-based reasoning which can be implemented directly in Prolog and CHR with a straightforward use of available and efficiently implemented facilities.The present paper clarifies the semantic foundations for this way of doing abduction in CHR and Prolog as well as other examples of hypothesis-based reasoning that is possible, including assumptive logic programming, hypotheses with priority and scope, and nonmonotonic reasoning.Examples are presented as executable code so the paper may also serve the additional purpose of a practical guide for developing such programs, and it is demonstrated that the approach provides a seamless integration with existing constraint solvers.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

HYPROLOG; Smodels
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdennadher, S.; Christiansen, H., An experimental CLP platform for integrity constraints and abduction, (Proceedings of FQAS2000, Flexible Query Answering Systems: Advances in Soft Computing Series (2000), Physica-Verlag (Springer)), 141-152
[2] Abdennadher, S.; Schütz, H., \(CHR^∨\): A flexible query language, (Andreasen, T.; Christiansen, H.; Larsen, H. L., Flexible Query Answering Systems, FQAS’98. Flexible Query Answering Systems, FQAS’98, Lecture Notes in Computer Science, vol. 1495 (1998), Springer), 1-14
[3] S. Baselice, P.A. Bonatti, M. Gelfond, Towards an integration of answer set and constraint solving, in: Gabbrielli and Gupta [35]; S. Baselice, P.A. Bonatti, M. Gelfond, Towards an integration of answer set and constraint solving, in: Gabbrielli and Gupta [35] · Zbl 1165.68481
[4] Betz, H.; Frühwirth, T. W., A linear-logic semantics for constraint handling rules, (van Beek, P., CP. CP, Lecture Notes in Computer Science, vol. 3709 (2005), Springer), 137-151 · Zbl 1153.68349
[5] Caroprese, L.; Trubitsyna, I.; Zumpano, E., Prioritized reasoning in logic programming, (Wilson, D.; Sutcliffe, G., FLAIRS Conference (2007), AAAI Press), 178-179
[6] Christiansen, H., Automated reasoning with a constraint-based metainterpreter, Journal of Logic Programmming, 37, 1-3, 213-254 (1998) · Zbl 0920.68098
[7] Christiansen, H., CHRG: A grammar notation based on Constraint Handling Rules (2002), Website with source code and examples for SICStus 3
[8] Christiansen, H., Reasoning about passive declarations in chr, (Schrijvers, T.; Frühwirth, T., Proceedings of CHR 2005, Second Workshop on Constraint Handling Rules. Proceedings of CHR 2005, Second Workshop on Constraint Handling Rules, Report CW, vol. 421 (2005), Department of Computer Science, Katholieke Universiteit: Department of Computer Science, Katholieke Universiteit Leuven, Belgium), 93-108
[9] Christiansen, H., CHR grammars, International Journal on Theory and Practice of Logic Programming, 5, 4-5, 467-501 (2005) · Zbl 1104.68055
[10] Christiansen, H., HYPROLOG: A logic programming language with assumptions and abduction. version 0.0 (2005), Website with source code and examples for SICStus 3 · Zbl 1165.68327
[11] Christiansen, H., On the implementation of global abduction, (Inoue, K.; Satoh, K.; Toni, F., CLIMA VII. CLIMA VII, Lecture Notes in Computer Science, vol. 4371 (2006), Springer), 226-245 · Zbl 1177.68200
[12] Christiansen, H., Logic programming as a framework for knowledge representation and artificial intelligence (2006), Teaching note for the course “Artificial Intelligence and Intelligent Systems”, Roskilde University, Denmark
[13] Christiansen, H.; Dahl, V., Logic grammars for diagnosis and repair, International Journal on Artificial Intelligence Tools, 12, 3, 227-248 (2003)
[14] H. Christiansen, V. Dahl, HYPROLOG: A new logic programming language with assumptions and abduction, in: Gabbrielli and Gupta [35]; H. Christiansen, V. Dahl, HYPROLOG: A new logic programming language with assumptions and abduction, in: Gabbrielli and Gupta [35] · Zbl 1165.68327
[15] H. Christiansen, V. Dahl, Meaning in context, in: A. Dey, B. Kokinov, D. Leake, R. Turner (Eds.), Proceedings of Fifth International and Interdisciplinary Conference on Modeling and Using Context (CONTEXT-05), in: Lecture Notes in Artificial Intelligence, vol. 3554, 2005, pp. 97-111; H. Christiansen, V. Dahl, Meaning in context, in: A. Dey, B. Kokinov, D. Leake, R. Turner (Eds.), Proceedings of Fifth International and Interdisciplinary Conference on Modeling and Using Context (CONTEXT-05), in: Lecture Notes in Artificial Intelligence, vol. 3554, 2005, pp. 97-111 · Zbl 1081.68706
[16] Christiansen, H.; Have, C. T.; Tveitane, K., From use cases to UML class diagrams using logic grammars and constraints, (Angelova, G.; Bontcheva, K.; Mitkov, R.; Nicolov, N.; Nikolov, N., RANLP 2007, International Conference: Recent Advances in Natural Language Processing: Proceedings. RANLP 2007, International Conference: Recent Advances in Natural Language Processing: Proceedings, Shoumen, Bulgaria (2007), INCOMA Ltd), 128-132
[17] Christiansen, H.; Have, C. T.; Tveitane, K., Reasoning about use cases using logic grammars and constraints, (Christiansen, H.; Villadsen, J., Proceedings of the 4th International Workshop on Constraints and Language Processing, CSLP 2007. Proceedings of the 4th International Workshop on Constraints and Language Processing, CSLP 2007, Computer Science Research Report, vol. 113 (2007), Roskilde University), 40-52
[18] Christiansen, H.; Martinenghi, D., DemoII System (1999), Website with source code and examples for SICStus 3.7
[19] Christiansen, H.; Martinenghi, D., Symbolic constraints for meta-logic programming, Applied Artificial Intelligence, 14, 4, 345-367 (2000)
[20] Clark, K. L., Negation as failure, (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum Press), 293-322
[21] Console, L.; Dupré, D. T.; Torasso, P., On the relationship between abduction and deduction, Journal of Logic and Computation, 1, 5, 661-690 (1991) · Zbl 0734.68085
[22] Dahl, V., An abductive treatment of long distance dependencies in chr, (Christiansen, H.; Skadhauge, P. R.; Villadsen, J., Constraint Solving and Language Processing. Constraint Solving and Language Processing, Lecture Notes in Computer Science, vol. 3438 (2004), Springer), 17-31
[23] Dahl, V.; Blache, P., Implantation de grammaires de propriétés en CHR, (Mesnard, F., Programmation en logique avec contraintes, JFPLC 2004 (2004), Hermes)
[24] Dahl, V.; Gu, B., Semantic property grammars for knowledge extraction from biomedical text, (Etalle, S.; Truszczynski, M., ICLP. ICLP, Lecture Notes in Computer Science, vol. 4079 (2006), Springer), 442-443 · Zbl 1131.68465
[25] Dahl, V.; Tarau, P.; Li, R., Assumption grammars for processing natural language, (Logic Programming, Proceedings of the Fourteenth International Conference on Logic Programming (1997), MIT Press), 256-270
[26] Denecker, M.; Kakas, A. C., Journal of Logic Programming, 44, 1-3 (2000), Special issue: abductive logic programming
[27] Denecker, M.; Kakas, A. C., Abduction in logic programming, (Kakas, A. C.; Sadri, F., Computational Logic: Logic Programming and Beyond. Computational Logic: Logic Programming and Beyond, Lecture Notes in Computer Science, vol. 2407 (2002), Springer), 402-436 · Zbl 1012.68503
[28] Dijkstra, E. W., Hierarchical ordering of sequential processes, Acta Informatica, 1, 115-138 (1971)
[29] Duck, G. J.; Stuckey, P. J.; de la Banda, M. J.G.; Holzbaur, C., The refined operational semantics of Constraint Handling Rules, (Demoen, B.; Lifschitz, V., Logic Programming, 20th International Conference, ICLP 2004, Proceedings. Logic Programming, 20th International Conference, ICLP 2004, Proceedings, Saint-Malo, France, September 6-10, 2004. Logic Programming, 20th International Conference, ICLP 2004, Proceedings. Logic Programming, 20th International Conference, ICLP 2004, Proceedings, Saint-Malo, France, September 6-10, 2004, Lecture Notes in Computer Science, vol. 3132 (2004), Springer), 90-104 · Zbl 1104.68359
[30] Enderton, H. B., A Mathematical Introduction to Logic (1972), Academic Press · Zbl 0298.02002
[31] Fernández, A. J.; Hill, P. M., A comparative study of eight constraint programming languages over the boolean and finite domains, Constraints, 5, 3, 275-301 (2000) · Zbl 0954.68031
[32] Frühwirth, T., Theory and practice of constraint handling rules, special issue on constraint logic programming, Journal of Logic Programming, 37, 1-3, 95-138 (1998) · Zbl 0920.68029
[33] T.A. Frühwirth, Description logic and rules the CHR way, in: K. Djelloul, G.J. Duck, M. Sulzmann (Eds.), Proceedings of the 4th Workshop on Constraint Handling Rules, CHR 2007, 2007, pp. 49-61; T.A. Frühwirth, Description logic and rules the CHR way, in: K. Djelloul, G.J. Duck, M. Sulzmann (Eds.), Proceedings of the 4th Workshop on Constraint Handling Rules, CHR 2007, 2007, pp. 49-61
[34] Fung, T. H.; Kowalski, R. A., The iff proof procedure for abductive logic programming, Journal of Logic Programmming, 33, 2, 151-165 (1997) · Zbl 0890.68029
[35] (Gabbrielli, M.; Gupta, G., Logic Programming, 21st International Conference, ICLP 2005, Proceedings. Logic Programming, 21st International Conference, ICLP 2005, Proceedings, Sitges, Spain, October 2-5, 2005. Logic Programming, 21st International Conference, ICLP 2005, Proceedings. Logic Programming, 21st International Conference, ICLP 2005, Proceedings, Sitges, Spain, October 2-5, 2005, Lecture Notes in Computer Science, vol. 3668 (2005), Springer) · Zbl 1086.68004
[36] Gavanelli, M.; Lamma, E.; Mello, P.; Torroni, P., An abductive framework for information exchange in multi-agent systems, (Dix, J.; Leite, J. A., CLIMA IV. CLIMA IV, Lecture Notes in Computer Science, vol. 3259 (2004), Springer), 34-52 · Zbl 1110.68503
[37] Hobbs, J. R.; Stickel, M. E.; Appelt, D. E.; Martin, P. A., Interpretation as abduction, Artificial Intelligence, 63, 1-2, 69-142 (1993)
[38] C. Holzbaur, OFAI clp(q,r) Manual, Edition 1.3.3, Tech. Rep. TR-95-09, Austrian Research Institute for Artificial Intelligence, Vienna, 1995; C. Holzbaur, OFAI clp(q,r) Manual, Edition 1.3.3, Tech. Rep. TR-95-09, Austrian Research Institute for Artificial Intelligence, Vienna, 1995
[39] Integrating Answer Programming and Constraint Logic Programming, online proceedings
[40] Kakas, A. C.; Kowalski, R. A.; Toni, F., Abductive logic programming, Journal of Logic and Computation, 2, 719-770 (1993) · Zbl 0778.68081
[41] Kakas, A. C.; Kowalski, R. A.; Toni, F., The role of abduction in logic programming, (Gabbay, D.; Hogger, C.; Robinson, J., Handbook of Artificial Intelligence and Logic Programming, vol. 5 (1998), Clarendon Press), 235-324
[42] Kakas, A. C.; Mancarella, P., Database updates through abduction, (McLeod, D.; Sacks-Davis, R.; Schek, H.-J., 16th International Conference on Very Large Data Bases, VLDB (1990), Morgan Kaufmann), 650-661
[43] A.C. Kakas, P. Mancarella, Abductive logic programming, in: Proc. of the Workshop Logic Programming and Non-Monotonic Logic, LPNMR, 1990, pp. 49-61; A.C. Kakas, P. Mancarella, Abductive logic programming, in: Proc. of the Workshop Logic Programming and Non-Monotonic Logic, LPNMR, 1990, pp. 49-61
[44] Kakas, A. C.; Michael, A.; Mourlas, C., Aclp: Abductive constraint logic programming, Journal of Logic Programming, 44, 1-3, 129-177 (2000) · Zbl 0957.68017
[45] Kakas, A. C.; Nuffelen, B. V.; Denecker, M., A-system: Problem solving through abduction, (Nebel, B., IJCAI (2001), Morgan Kaufmann), 591-596
[46] Koninck, L. D.; Schrijvers, T.; Demoen, B., User-definable rule priorities for CHR, (Leuschel, M.; Podelski, A., Proceedings of the 9th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (2007), ACM), 25-36
[47] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The dlv system for knowledge representation and reasoning, ACM Transactions on Computational Logic, 7, 3, 499-562 (2006) · Zbl 1367.68308
[48] Lloyd, J. W., Foundations of Logic Programming, Springer Series in Symbolic Computation (1987), Springer-Verlag · Zbl 0547.68005
[49] Mancarella, P.; Sadri, F.; Terreni, G.; Toni, F., Programming applications in CIFF, (Baral, C.; Brewka, G.; Schlipf, J. S., LPNMR. LPNMR, Lecture Notes in Computer Science, vol. 4483 (2007), Springer), 284-289
[50] Mitkov, R., Anaphora Resolution (2002), Longman (Pearson Education) · Zbl 1045.68825
[51] Morawietz, F., Chart parsing and constraint programming, (COLING (2000), Morgan Kaufmann), 551-557
[52] F. Morawietz, P. Blache, Parsing natural languages with CHR, Unpublished (2002); F. Morawietz, P. Blache, Parsing natural languages with CHR, Unpublished (2002)
[53] Penn, G., Applying constraint handling rules to HPSG, in: Proceedings of the First International Conference on Computational Logic (CL2000), Workshop on Rule-based Constraint Reasoning and Programming, London, UK, 2000
[54] C. Sakama, K. Inoue, Representing priorities in logic programs, in: M.J. Maher (Ed.), Logic Programing, Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming, 1996, pp. 82-96; C. Sakama, K. Inoue, Representing priorities in logic programs, in: M.J. Maher (Ed.), Logic Programing, Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming, 1996, pp. 82-96
[55] Satoh, K., An application of global abduction to an information agent which modifies a plan upon failure—preliminary report, (Leite, J. A.; Torroni, P., CLIMA V. CLIMA V, Lecture Notes in Computer Science, vol. 3487 (2004), Springer), 213-229 · Zbl 1081.68689
[56] K. Satoh, “All”s well that ends well”—a proposal of global abduction, in: J.P. Delgrande, T. Schaub (Eds.), 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), 2004, pp. 360-367; K. Satoh, “All”s well that ends well”—a proposal of global abduction, in: J.P. Delgrande, T. Schaub (Eds.), 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), 2004, pp. 360-367
[57] Schrijvers, T., The Programming Language CHR, Constraint Handling Rules, (from 2005)
[58] Swedish Institute of Computer Science, (checked 2007)
[59] SWI Prolog Organization, (checked 2007)
[60] Syrjänen, T.; Niemelä, I., The Smodels system, (Eiter, T.; Faber, W.; Truszczynski, M., Proc. of the Workshop Logic Programming and Non-Monotonic Logic, LPNMR. Proc. of the Workshop Logic Programming and Non-Monotonic Logic, LPNMR, Lecture Notes in Computer Science, vol. 2173 (2001), Springer), 434-438 · Zbl 1010.68797
[61] Tarau, P., BinProlog, website · Zbl 1244.68022
[62] Zhang, Y., Two results for prioritized logic programming, Theory and Practice of Logic Programming, 3, 2, 223-242 (2003) · Zbl 1111.68387
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.