Advertisement

Declarative Problem-Solving Using the DLV System

  • Thomas Eiter
  • Wolfgang Faber
  • Nicola Leone
  • Gerald Pfeifer
Chapter
Part of the The Springer International Series in Engineering and Computer Science book series (SECS, volume 597)

Abstract

The need for representing indefinite information led to disjunctive deductive databases, which also fertilized work on disjunctive logic programming. Based on this paradigm, the DLV system has been designed and implemented as a tool for declarative knowledge representation. In this paper, we focus on the usage of DLV for solving problems in a declarative manner and report on experiments that we have run on a suite of benchmark problems. We discuss how problems can be solved in a natural way using a “Guess&Check”-paradigm where solutions are guessed and verified by parts of the program. Furthermore, we describe various front-ends that can be used for solving problems in specific applications. The experiments show that due to the ongoing implementation efforts, which include fine-tuning of the underlying algorithms, successive and significant performance improvements have been achieved during the last two years. The results indicate that DLV is capable of solving some complex problems quite efficiently.

Keywords

Disjunctive logic programming disjunctive databases nonmonotonic reasoning 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Apt, K. R., Blair, H. A., and Walker, A. (1988). Towards a theory of declarative knowledge. In Minker, J., editor, Foundations of Deductive Databases and Logic Programming, pages 89–148. Morgan Kaufmann Publishers, Inc., Los Altos, California.Google Scholar
  2. Aravindan, C., Dix, J., and Niemelä, I. (1997). Dislop: A research project on disjunctive logic programming. AI Communications, 10(3/4):151–165.Google Scholar
  3. Ben-Eliyahu, R. and Dechter, R. (1994). Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence, 12:53–87.MathSciNetzbMATHCrossRefGoogle Scholar
  4. Ben-Eliyahu, R. and Palopoli, L. (1994). Reasoning with minimal models: efficient algorithms and applications. In Proc. Fourth International Conf. on Principles of Knowledge Representation and Reasoning (KR-94), pages 39–50.Google Scholar
  5. Buccafurri, F., Faber, W., and Leone, N. (1999). Disjunctive logic programs with inheritance. In Schreye, D. D., editor, Proceedings of the 16th International Conference on Logic Programming (ICLP’99), pages 79–93, Las Cruces, New Mexico, USA. The MIT Press.Google Scholar
  6. Buccafurri, F., Leone, N., and Rullo, P. (1997). Strong and weak constraints in disjunctive Datalog. In Dix, J., Furbach, U., and Nerode, A., editors, Proceedings of the 4 th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR ’97), number 1265 in Lecture Notes in AI (LNAI), pages 2–17, Dagstuhl, Germany. Springer Verlag.Google Scholar
  7. Cadoli, M., Eiter, T., and Gottlob, G. (1997). Default logic as a query language. IEEE Transactions on Knowledge and Data Engineering, 9(3):448–463.CrossRefGoogle Scholar
  8. Cadoli, M., Palopoli, L., Schaerf, A., and Vasile, D. (1999). NP-SPEC: An executable specification language for solving all problems in NP. In Gupta, G., editor, Proceedings of the 1st International Workshop on Practical Aspects of Declarative Languages (PADL’99), number 1551 in Lecture Notes in Computer Science, pages 16–30. Springer.Google Scholar
  9. Chen, W. and Warren, D. S. (1996). Computation of stable models and its integration with logical query processing. IEEE Transactions on Knowledge and Data Engineering, 8(5):742–757.CrossRefGoogle Scholar
  10. Cholewiński, P., Marek, V. W., Mikitiuk, A., and Truszczyński, M. (1999). Computing with default logic. Artificial Intelligence, 112(2–3): 105–147.MathSciNetCrossRefGoogle Scholar
  11. Cholewiński, P., Marek, V. W., and Truszczyński, M. (1996). Default reasoning system DeReS. In Proceedings of International Conference on Principles of Knowledge Representation and Reasoning (KR’96), pages 518–528. Cambridge, Massachusetts, USA. Morgan Kaufmann Publishers.Google Scholar
  12. Dimopoulos, Y., Nebel, B., and Koehler, J. (1997). Encoding planning problems in nonmonotonic logic programs. In Proceedings of the European Conference on Planning 1997 (ECP-97), pages 169–181. Springer Verlag.Google Scholar
  13. Eiter, T., Faber, W., Leone, N., and Pfeifer, G. (1999). The diagnosis frontend of the DLV system. AI Communications — The European Journal on Artificial Intelligence, 12(1–2):99–l11.MathSciNetGoogle Scholar
  14. Eiter, T., Gottlob, G., and Leone, N. (1997a). Abduction from logic programs: Semantics and complexity. Theoretical Computer Science, 189(1–2):129–177.MathSciNetzbMATHCrossRefGoogle Scholar
  15. Eiter, T., Gottlob, G., and Mannila, H. (1994). Adding disjunction to Datalog. In Proc. of the Thirteenth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-94), pages 267–278. ACM Press.Google Scholar
  16. Eiter, T., Gottlob, G., and Mannila, H. (1997b). Disjunctive Datalog. ACM Transactions on Database Systems, 22(3):315–363.CrossRefGoogle Scholar
  17. Eiter, T., Leone, N., Mateis, C, Pfeifer, G., and Scarcello, F. (1997c). A deductive system for nonmonotonic reasoning. In Dix, J., Furbach, U., and Nerode, A., editors, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’97), number 1265 in Lecture Notes in AI (LNAI), pages 363–374, Berlin. Springer.CrossRefGoogle Scholar
  18. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1997d). The architecture of a disjunctive deductive database system. In Falaschi, M., Navarro, M., and Policriti, A., editors, Proceedings Joint Conference on Declarative Programming (APPIA-GULP-PRODE’97), pages 141–151.Google Scholar
  19. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1998a). Progress report on the disjunctive deductive database system DLV. In Andreasen, T., Christiansen, H., and Larsen, H. L., editors, Proc. International Conf. on Flexible Query Answering Systems (FQAS’98), number 1495 in Lecture Notes in AI (LNAI), pages 148–163, Roskilde University, Denmark. Springer.CrossRefGoogle Scholar
  20. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1998b). The KR system DLV: Progress report, comparisons and benchmarks. In Cohn, A. G., Schubert, L., and Shapiro, S. C., editors, Proceedings Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR’98), pages 406–417. Morgan Kaufmann Publishers.Google Scholar
  21. Erdem, E. (1999). Applications of logic programming to planning: Computational experiments. Unpublished draft, http://www.cs.utexas.edu/users/esra/papers.html.Google Scholar
  22. Erdem, E. (since 1998). Website for applications of logic programming to planning: Computational experiments. http://www.cs.utexas.edu/users/esra/experiments/experiments.html.Google Scholar
  23. Faber, W. (1998). Disjunctive Datalog with strong and weak constraints: Representational and computational issues. Master’s thesis, Institut für Informationssysteme, Technische Universität Wien.Google Scholar
  24. Faber, W. (1999). DLV homepage. <URL: http://www.dbai.tuwien.ac.at/proj/dlv/inheritance/>.
  25. Faber, W., Leone, N., Mateis, C., and Pfeifer, G. (1999a). Using database optimization techniques for monmonotonic reasoning. In Committee, I. O., editor, Proceedings of the 7th International Workshop on Deductive Databases and Logic Programming (DDLP’99), pages 135–139. Prolog Association of Japan.Google Scholar
  26. Faber, W., Leone, N., and Pfeifer, G. (1999b). Pushing goal derivation in DLP computations. In Gelfond, M., Leone, N., and Pfeifer, G., editors, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’99), number 1730 in Lecture Notes in AI (LNAI), pages 177–191, El Paso, Texas, USA. Springer Verlag.Google Scholar
  27. Faber, W. and Pfeifer, G. (since 1996). dlv homepage. <URL:http://www.dbai.tuwien.ac.at/proj/dlv/>.
  28. Gelfond, M. and Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365–385.CrossRefGoogle Scholar
  29. Janhunen, T., Niemela, I., Simons, P., and You, J.-H. (2000). Partiality and disjunctions in stable model semantics. In Cohn, A. G., Giunchiglia, F., and Selman, B., editors, Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000), pages 411–419, Breckenridge, Colorado, USA. Morgan Kaufmann Publishers, Inc.Google Scholar
  30. Koch, C. (1999). A simple query facility for the objectivity/db persistent object manager. Unpublished draft, available via the author’s homepage <URL: http://home.cern.ch/~chkoch/>.Google Scholar
  31. Koch, C. and Leone, N. (1999). Stable model checking made easy. In Dean, T., editor, The International Joint Conferences on Artificial Intelligence (IJ-CAI) 1999, pages 70–75, Stockholm, Sweden. Morgan Kaufmann Publishers.Google Scholar
  32. Leone, N., Rullo, P., and Scarcello, F. (1997). Disjunctive stable models: Unfounded sets, fixpoint semantics and computation. Information and Computation, 135(2):69–112.MathSciNetzbMATHCrossRefGoogle Scholar
  33. Lifschitz, V. (1996). Foundations of logic programming. In Brewka, G., editor, Principles of Knowledge Representation, pages 69–127. CSLI Publications, Stanford.Google Scholar
  34. Lifschitz, V. (1999a). Action languages, answer sets and planning. In Apt, K., Marek, V. W., Truszczyński, M., and Warren, D. S., editors, The Logic Programming Paradigm — A 25-Year Perspective, pages 357–373. Springer Verlag.Google Scholar
  35. Lifschitz, V. (1999b). Answer set planning. In Schreye, D. D., editor, Proceedings of the 16th International Conference on Logic Programming (ICLP’99), pages 23–37, Las Cruces, New Mexico, USA. The MIT Press.Google Scholar
  36. Lifschitz, V. and Turner, H. (1994). Splitting a logic program. In Van Hentenryck, P., editor, Proceedings of the 11th International Conference on Logic Programming (ICLP’94), pages 23–37, Santa Margherita Ligure, Italy. MIT Press.Google Scholar
  37. Lobo, J., Minker, J., and Rajasekar, A. (1992). Foundations of Disjunctive Logic Programming. The MIT Press, Cambridge, Massachusetts.Google Scholar
  38. Marek, V. W. and Truszczyński, M. (1999). Stable models and an alternative logic programming paradigm. In Apt, K., Marek, V. W., Truszczyński, M., and Warren, D. S., editors, The Logic Programming Paradigm — A 25-Year Perspective, pages 375–398. Springer Verlag.Google Scholar
  39. McCain, N. (1999). The clausal calculator homepage.<URL:http://www.cs.utexas.edu/users/mccain/cc/>.
  40. Minker, J. (1994). Overview of disjunctive logic programming. Annals of Mathematics and Artificial Intelligence, 12:1–24.MathSciNetCrossRefGoogle Scholar
  41. Niemelä, I. (1999). Logic programming with stable model semantics as constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3–4):241–273.MathSciNetzbMATHCrossRefGoogle Scholar
  42. Niemelä, I. and Simons, P. (1996). Efficient implementation of the well-founded and stable model semantics. In Maher, M. J., editor, Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming (ICLP’96), pages 289–303, Bonn, Germany. MIT Press.Google Scholar
  43. Niemelä, I. and Simons, P. (1997). Smodels — an implementation of the stable model and well-founded semantics for normal logic programs. In Dix, J., Furbach, U., and Nerode, A., editors, Proceedings of the 4th Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’97), volume 1265 of Lecture Notes in AI (LNAI), pages 420–429, Dagstuhl, Germany. Springer Verlag.CrossRefGoogle Scholar
  44. Poole, D. (1989). Explanation and prediction: An architecture for default and abductive reasoning. Computational Intelligence, 5(1):97–110.MathSciNetCrossRefGoogle Scholar
  45. Przymusinski, T. C. (1991). Stable semantics for disjunctive programs. New Generation Computing, 9:401–424.CrossRefGoogle Scholar
  46. Rao, P., Sagonas, K. F., Swift, T., Warren, D. S., and Freire, J. (1997). XSB: A system for efficiently computing well-founded semantics. In Dix, J., Furbach, U., and Nerode, A., editors, Proceedings of the 4th Int. Conf. on Logic Programming and Non-Monotonic Reasoning (LPNMR’97), number 1265 in Lecture Notes in AI (LNAI), pages 2–17, Dagstuhl, Germany. Springer Verlag.Google Scholar
  47. Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32:57–95.MathSciNetzbMATHCrossRefGoogle Scholar
  48. Seipel, D. and Thöne, H. (1994). DisLog — A system for reasoning in disjunctive deductive databases. In Olivé, A., editor, Proceedings International Workshop on the Deductive Approach to Information Systems and Databases (DAISD’94), pages 325–343. Universitat Politecnica de Catalunya (UPC).Google Scholar
  49. Subrahmanian, V. and Zaniolo, C. (1995). Relating stable models and AI planning domains. In Sterling, L., editor, Proceedings of the 12 th International Conference on Logic Programming, pages 233–247, Tokyo, Japan. MIT Press.Google Scholar
  50. Turner, H. (1997). Representing actions in logic programs and default theories: A situation calculus approach. Journal of Logic Programming, 31(1–3):245–298.MathSciNetzbMATHCrossRefGoogle Scholar
  51. 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.zbMATHGoogle Scholar
  52. Winston, P. H. (1992). Artificial Intelligence. Addison Wesley.Google Scholar

Copyright information

© Springer Science+Business Media New York 2000

Authors and Affiliations

  • Thomas Eiter
    • 1
  • Wolfgang Faber
    • 1
  • Nicola Leone
    • 1
  • Gerald Pfeifer
    • 1
  1. 1.Information Systems DepartmentTechnische UniversitätWienAustria

Personalised recommendations