Pruning Operators for Disjunctive Logic Programming Systems

• Autorzy: Calimeri F. , Faber W. , Pfeifer G. , Leone N.
• Języki publikacji: EN

Abstrakty

EN

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class \SigmaP2 = \NP\NP). The DLP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process commonly performed by DLP systems, with a focus on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV - the state-of-the-art DLP system - and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems.

Słowa kluczowe

EN

artificial intelligence; Disjunctive Logic Programming; DLP; non-monotonic reasoning; DLP computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 2,3
• Strony: 183--214
• Opis fizyczny: tab., bibliogr. 51 poz.

Twórcy

autor

Calimeri F.

autor

Faber W.

autor

Pfeifer G.

autor

Leone N.

• Department of Mathematics , University of Calabria 87030 Rende (CS), Italy,

Bibliografia

• [1] Anger, C., Konczak, K., Linke, T.: NoMoRe : A System for Non-Monotonic Reasoning, Logic Programming and Nonmonotonic Reasoning - 6th International Conference, LPNMR'01, Vienna, Austria, September 2001, Proceedings (T. Eiter, W. Faber, M. Truszczyński, Eds.), number 2173 in Lecture Notes in AI (LNAI), Springer Verlag, September 2001.
• [2] Apt, K., Bol, N.: Logic Programming and Negation: A Survey, Journal of Logic Programming, 19/20, 1994, 9-71.
• [3] Aravindan, C., Dix, J., Niemelä, I.: DisLoP: A Research Project on Disjunctive Logic Programming, AI Communications - The European Journal on Artificial Intelligence, 10(3/4), 1997, 151-165.
• [4] Babovich, Y.: Cmodels homepage, since 2002, http://cs.utexas.edu/usera/tag/cmodels.html.
• [5] Bell, C., Nerode, A., Ng, R. T., Subrahmanian, V.: Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases, Journal of the ACM, 41, 1994, 1178-1215.
• [6] Ben-Eliyahu, R., Dechter, R.: Propositional Semantics for Disjunctive Logic Programs, Annals of Mathematics and Artificial Intelligence, 12, 1994, 53-87.
• [7] Berman, K. A., Schlipf, J. S., Franco, J. V.: Computing the Well-Founded Semantics Faster, Proceedings of the 3rd International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'95), 928, Springer, 1995.
• [8] Brass, S., Dix, J., Freitag, B., Zukowski, U.: Transformation-Based Bottom-Up Computation of the Well-Founded Model, Journal of the Theory and Practice of Logic Programming, 1(5), 2001, 497-538.
• [9] Calimeri, F.: Progettazione e Sviluppo di Tecniche Di Ottimizzazione per Sistemi di Basi di Conoscenza, Master Thesis, D.E.I.S., Universit`a degli Studi della Calabria, Rende (CS), Italy, 2001, Supported by Nicola Leone.
• [10] Chen, W., Warren, D. S.: Computation of Stable Models and Its Integration with Logical Query Processing, IEEE Transactions on Knowledge and Data Engineering, 8(5), 1996, 742-757.
• [11] Cholewiński, P., Marek, V. W., Mikitiuk, A., Truszczyński, M.: Computing with Default Logic, Artificial Intelligence, 112(2-3), 1999, 105-147.
• [12] Cholewiński, P., Marek, V.W., Truszczyński, M.: Default Reasoning System DeReS, Proceedings of International Conference on Principles of Knowledge Representation and Reasoning (KR '96), Morgan Kaufmann Publishers, Cambridge, Massachusetts, USA, 1996.
• [13] Dix, J.: Semantics of Logic Programs: Their Intuitions and Formal Properties. An Overview, Logic, Action and Information. Proceedings of the Konstanz Colloquium in Logic and Information (LogIn'92), DeGruyter, 1995.
• [14] Dowling, W. F., Gallier, J. H.: Linear-time Algorithms for Testing the Satisfability of Propositional Horn Formulae, Journal of Logic Programming, 3, 1984, 267-284.
• [15] East, D., Truszczyński, M.: dcs: An Implementation of DATALOG with Constraints, Proceedings of the 8th International Workshop on Non-Monotonic Reasoning (NMR'2000) (C. Baral, M. Truszczyński, Eds.), Breckenridge, Colorado, USA, April 2000.
• [16] East, D., Truszczyński, M.: Propositional Satisfiability in Answer-set Programming., Proceedings of Joint German/Austrian Conference on Artificial Intelligence, KI'2001, Springer Verlag, LNAI 2174, 2001.
• [17] East, D., Truszczyński, M.: System Description: aspps - An Implementation of Answer-Set Programming with Propositional Schemata, Logic Programming and Nonmonotonic Reasoning - 6th International Conference, LPNMR'01, Vienna, Austria, September 2001, Proceedings (T. Eiter, W. Faber, M. Truszczyński, Eds.), number 2173 in Lecture Notes in AI (LNAI), Springer Verlag, September 2001.
• [18] Egly, U., Eiter, T., Tompits, H., Woltran, S.: Solving Advanced Reasoning Tasks using Quantified Boolean Formulas, Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI'00), July 30 - August 3, 2000, Austin, Texas USA, AAAI Press / MIT Press, 2000.
• [19] Eiter, T., Faber, W., Leone, N., Pfeifer, G.: Declarative Problem-Solving Using the DLV System, in: Logic-Based Artificial Intelligence (J. Minker, Ed.), Kluwer Academic Publishers, 2000, 79-103.
• [20] Eiter, T., Gottlob, G., Mannila, H.: Disjunctive Datalog, ACM Transactions on Database Systems, 22(3), September 1997, 364-418.
• [21] Erdem, E.: Applications of Logic Programming to Planning: Computational Experiments, 1999, Unpublished draft. http://cs.utexas.edu/users/esra/papers.html.
• [22] Faber, W.: Enhancing Efficiency and Expressiveness in Answer Set Programming Systems, Ph.D. Thesis, Institut für Informationssysteme, Technische Universität Wien, 2002.
• [23] Faber, W., Leone, N., Mateis, C., Pfeifer, G.: Using Database Optimization Techniques for Nonmonotonic Reasoning, Proceedings of the 7th InternationalWorkshop on Deductive Databases and Logic Programming (DDLP'99) (INAP Organizing Committee, Ed.), Prolog Association of Japan, September 1999.
• [24] Faber,W., Leone, N., Pfeifer, G.: Experimenting with Heuristics for Answer Set Programming, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI) 2001, Morgan Kaufmann Publishers, Seattle, WA, USA, August 2001.
• [25] Fages, F.: Consistency of Clark's Completion and Existence of Stable Models, Journal of Methods of Logic in Computer Science, 1(1), 1994, 51-60.
• [26] Fitting, M.: A Kripke-Kleene Semantics for Logic Programs, Journal of Logic Programming, 2(4), 1985, 295-312.
• [27] Gelfond, M., Leone, N.: Logic Programming and Knowledge Representation - the A-Prolog perspective , Artificial Intelligence, 138(1-2), 2002, 3-38.
• [28] Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, 9, 1991, 365-385.
• [29] Janhunen, T., Niemelä, I., Seipel, D., Simons, P., You, J.-H.: Unfolding Partiality and Disjunctions in Stable Model Semantics, ACM Transactions on Computational Logic, 2005, To appear.
• [30] Kautz, H., Selman, B.: Planning as Satisfiability, Proceedings of the 10th European Conference on Artificial Intelligence (ECAI '92), 1992.
• [31] 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, 2005, To appear. Available via http://arxiv.org/ps/cs.A1/0211004.
• [32] Leone, N., Romeo, M., Rullo, P., Sacc`a, D.: Effective Implementation of Negation in Database Logic Query Languages, LOGIDATA+: Deductive Database with Complex Objects, LNCS 701, 1993.
• [33] Leone, N., Rullo, P., Scarcello, F.: Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics and Computation, Information and Computation, 135(2), June 1997, 69-112.
• [34] Lierler, Y.: Disjunctive Answer Set Programming via Satisfiability, Proceedings of the 8th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'05) (C. Baral, G. Greco, N. Leone, G. Terracina, Eds.), LNCS, Springer, September 2005.
• [35] Lierler, Y., Maratea, M.: Cmodels-2: SAT-based Answer Set Solver Enhanced to Non-tight Programs, Proceedings of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR-7) (V. Lifschitz, I. Niemelä, Eds.), LNCS, Springer, January 2004.
• [36] Lifschitz, V.: Answer Set Planning, Proceedings of the 16th International Conference on Logic Programming (ICLP'99) (D. D. Schreye, Ed.), The MIT Press, Las Cruces, New Mexico, USA, November 1999.
• [37] Lifschitz, V., Turner, H.: Splitting a Logic Program, Proceedings of the 11th International Conference on Logic Programming (ICLP'94) (P. Van Hentenryck, Ed.), MIT Press, Santa Margherita Ligure, Italy, June 1994.
• [38] Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by SAT solvers., Artificial Intelligence, 157(1-2), 2004, 115-137.
• [39] McCain, N., Turner, H.: Satisfiability Planning with Causal Theories, Proceedings Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98) (A. G. Cohn, L. Schubert, S. C. Shapiro, Eds.), Morgan Kaufmann Publishers, 1998.
• [40] Minoux, M.: LTUR: A Simplified Linear-time Unit Resolution Algorithm for Horn Formulae and Computer Implementation, Information Processing Letters, 29, 1988, 1-12.
• [41] Niemelä, I.: Logic Programming with Stable Model Semantics as Constraint Programming Paradigm, Annals of Mathematics and Artificial Intelligence, 25(3-4), 1999, 241-273.
• [42] Niemelä, I., Simons, P.: Efficient Implementation of the Well-founded and Stable Model Semantics, Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming (ICLP'96) (M. J. Maher, Ed.), MIT Press, Bonn, Germany, September 1996.
• [43] Niemelä, I., Simons, P.: Smodels - An Implementation of the Stable Model and Well-founded Semantics for Normal Logic Programs, Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97) (J. Dix, U. Furbach, A. Nerode, Eds.), 1265, Springer Verlag, Dagstuhl, Germany, July 1997.
• [44] Radziszowski, S. P.: Small Ramsey Numbers, The Electronic Journal of Combinatorics, 1, 1994, Revision 9: July 15, 2002.
• [45] Rao, P., Sagonas, K. F., Swift, T., Warren, D. S., Freire, J.: XSB: A System for Efficiently Computing Well-Founded Semantics, Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'97) (J. Dix, U. Furbach, A. Nerode, Eds.), number 1265 in Lecture Notes in AI (LNAI), Springer Verlag, Dagstuhl, Germany, July 1997.
• [46] Seipel, D., Thöne, H.: DisLog - A System for Reasoning in Disjunctive Deductive Databases., Proceedings InternationalWorkshop on the Deductive Approach to Information Systems and Databases (DAISD'94) (A. Olivé, Ed.), Universitat Politecnica de Catalunya (UPC), 1994.
• [47] Simons, P.: Extending and Implementing the Stable Model Semantics, Ph.D. Thesis, Helsinki University of Technology, Finland, 2000.
• [48] Simons, P., Niemelä, I., Soininen, T.: Extending and Implementing the Stable Model Semantics, Artificial Intelligence, 138, June 2002, 181-234.
• [49] Subrahmanian, V., Nau, D., Vago, C.: WFS + Branch and Bound = Stable Models, IEEE Transactions on Knowledge and Data Engineering, 7(3), June 1995, 362-377.
• [50] Tarjan, R.: Depth-First Search and Linear Graph Algorithm, SIAM Journal on Computing, 1(2), June 1972.
• [51] Van Gelder, A., Ross, K., Schlipf, J.: The Well-Founded Semantics for General Logic Programs, Journal of the ACM, 38(3), 1991, 620-650.