The DLV system for knowledge representation and reasoning

Abstract

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning, which is very expressive in a precise mathematical sense: it allows one to express every property of finite structures that is decidable in the complexity class Σ^P₂ (NP^NP). Thus, under widely believed assumptions, DLP is strictly more expressive than normal (disjunction-free) logic programming, whose expressiveness is limited to properties decidable in NP. Importantly, apart from enlarging the class of applications which can be encoded in the language, disjunction often allows for representing problems of lower complexity in a simpler and more natural fashion.This article presents the DLV system, which is widely considered the state-of-the-art implementation of disjunctive logic programming, and addresses several aspects. As for problem solving, we provide a formal definition of its kernel language, function-free disjunctive logic programs (also known as disjunctive datalog), extended by weak constraints, which are a powerful tool to express optimization problems. We then illustrate the usage of DLV as a tool for knowledge representation and reasoning, describing a new declarative programming methodology which allows one to encode complex problems (up to Δ^P₃-complete problems) in a declarative fashion. On the foundational side, we provide a detailed analysis of the computational complexity of the language of DLV, and by deriving new complexity results we chart a complete picture of the complexity of this language and important fragments thereof.Furthermore, we illustrate the general architecture of the DLV system, which has been influenced by these results. As for applications, we overview application front-ends which have been developed on top of DLV to solve specific knowledge representation tasks, and we briefly describe the main international projects investigating the potential of the system for industrial exploitation. Finally, we report about thorough experimentation and benchmarking, which has been carried out to assess the efficiency of the system. The experimental results confirm the solidity of DLV and highlight its potential for emerging application areas like knowledge management and information integration.

References

1. Anger, C., Konczak, K., and Linke, T. 2001. NoMoRe: A system for non-monotonic reasoning. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'01), Vienna, Austria, T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 2173. Springer, Berlin, Germany, 406--410.]]
2. Apt, K. and Bol, N. 1994. Logic programming and negation: A survey. J. Logic Programm. 19/20, 9--71.]]
3. Apt, K. R., Blair, H. A., and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Morgan Kaufmann, San Francisco, CA, 89--148.]]
4. Aravindan, C., Dix, J., and Niemelä, I. 1997. Dislop: A research project on disjunctive logic programming. AI Commun. Europ. J. Artific. Intell. 10, 3/4, 151--165.]]
5. Babovich, Y. 2002. Cmodels homepage. http://www.cs.utexas.edu/users/tag/cmodels.html.]]
6. Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge, U.K.]]
7. Baral, C. and Gelfond, M. 1994. Logic programming and knowledge representation. J. Logic Programm. 19/20, 73--148.]]
8. Ben-Eliyahu, R. and Dechter, R. 1994. Propositional semantics for disjunctive logic programs. Ann. Math. Artific. Intell. 12, 53--87.]]
9. Ben-Eliyahu, R. and Palopoli, L. 1994. Reasoning with minimal models: Efficient algorithms and applications. In Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR-94). 39--50.]]
10. Brass, S. and Dix, J. 1995. Disjunctive semantics based upon partial and bottom-up evaluation. In Proceedings of the 12th International Conference on Logic Programm., Tokyo, Japan, L. Sterling, Ed. MIT Press, Cambridge, MA, 199--213.]]
11. Brewka, G. and Eiter, T. 1999. Preferred answer sets for extended logic programs. Artific. Intell. 109, 1-2, 297--356.]]
12. Brewka, G., Niemelä, I., Schaub, T., and Truszczyński, M. (organizers). 2002. Dagstuhl Seminar Nr. 0238, Nonmonotonic Reasoning, Answer Set Programming and Constraints, September 15--20, 2002. System Competition. Go online to http://www.cs.uni-potsdam.de/~canger/dagstuhl.html.]]
13. Buccafurri, F., Faber, W., and Leone, N. 2002. Disjunctive logic programs with inheritance. Theor. Pract. Logic Programm. 2, 3.]]
14. Buccafurri, F., Leone, N., and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12, 5, 845--860.]]
15. Cadoli, M., Eiter, T., and Gottlob, G. 1997a. Default logic as a query language. IEEE Trans. Knowl. Data Eng. 9, 3 (May/June), 448--463.]]
16. Cadoli, M., Giovanardi, A., and Schaerf, M. 1997b. Experimental analysis of the computational cost of evaluating quantified boolean formulae. In Proceedings of the 5th Congress of the Italian Association for Artificial Intelligence (AI*IA 97), Rome, Italy. Lecture Notes in Computer Science 1321, Springer, Berlin, Germany, 207--218.]]
17. Calimeri, F., Faber, W., Leone, N., and Pfeifer, G. 2002. Pruning operators for answer set programming systems. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR'2002). 200--209.]]
18. Chen, W. and Warren, D. S. 1996. Computation of stable models and its integration with logical query processing. IEEE Trans. Knowl. Data Eng. 8, 5, 742--757.]]
19. Cholewiński, P., Marek, V. W., Mikitiuk, A., and Truszczyński, M. 1999. Computing with default logic. Artific. Intell. 112, 2--3, 105--147.]]
20. Cholewiński, P., Marek, V. W., and Truszczyński, M. 1996. Default reasoning system DeReS. In Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR '96), Cambridge, MA. Morgan Kaufmann, San Francisco, CA, 518--528.]]
21. Clark, K. 1978. Negation as failure. In Logic and Data Bases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, NY, 293--322.]]
22. Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374--425.]]
23. Delgrande, J., Schaub, T., and Tompits, H. 2001. plp: A generic compiler for ordered logic programs. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-01), T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in Computer Science, vol. 2173, Springer, Berlin, Germany, 411--415.]]
24. Dell'Armi, T., Faber, W., Ielpa, G., Leone, N., and Pfeifer, G. 2003. Aggregate functions in disjunctive logic programm: Semantics, complexity, and implementation in DLV. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico. Morgan Kaufmann, San Francisco, CA.]]
25. Dix, J. 1995. Semantics of logic programs: Their intuitions and formal properties. An overview. In Logic, Action and Information. Proceedings of the Konstanz Colloquium in Logic and Information (LogIn'92). Walter de Gruyter, Berlin, Germany, 241--329.]]
26. Dix, J. and Furbach, U. 1996. The DFG project DisLoP on disjunctive logic programming. Computat. Logic 2, 2, 89--90.]]
27. Dix, J., Gottlob, G., and Marek, V. W. 1996. Reducing disjunctive to non-disjunctive semantics by shift-operations. Fundamenta Informaticae 28, 87--100.]]
28. Dix, J., Kuter, U., and Nau, D. 2002. Planning in answer set programming using ordered task decomposition. Theo. Pract. Logic Programm. Revised paper submitted for publication.]]
29. East, D. and Truszczyński, M. 2000. dcs: An implementation of DATALOG with constraints. In Proceedings of the 8th International Workshop on Non-Monotonic Reasoning (NMR'2000), Breckenridge, Colorado, USA, C. Baral and M. Truszczyński, Eds.]]
30. East, D. and Truszczyński, M. 2001a. System description: aspps---An implementation of answer-set programming with propositional schemata. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'01), Vienna, Austria, T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in Artificial Intelligence, vol. 2173. Springer, Berlin, Germany, 402--405.]]
31. East, D. and Truszczyński, M. 2001b. Propositional satisfiability in answer-set programming. In Proceedings of the Joint German/Austrian Conference on Artificial Intelligence, KI'2001. Lecture Notes in Arificial Intelligence, vol. 2174. Springer Verlag, Berlin, Germany, 138--153.]]
32. Egly, U., Eiter, T., Tompits, H., and Woltran, S. 2000. Solving advanced reasoning tasks using quantified boolean formulas. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00), July 30--August 3, 2000, Austin, Texas USA. AAAI Press Stanford, CA/MIT Press, Cambridge, MA, 417--422.]]
33. Eiter, T., Faber, W., Gottlob, G., Koch, C., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. 1999. The DLV system. In Workshop on Logic-Based Artificial Intelligence, Washington, DC, J. Minker, Ed. Computer Science Department, University of Maryland, College Park, MD. Workshop notes.]]
34. Eiter, T., Faber, W., Leone, N., and Pfeifer, G. 2000a. Declarative problem-solving using the DLV system. In Logic-Based Artificial Intelligence, J. Minker, Ed. Kluwer Academic Press, New York, NY, 79--103.]]
35. Eiter, T., Faber, W., Leone, N., and Pfeifer, G. 2001a. Computing preferred and weakly preferred answer sets by meta-interpretation in answer set programming. In Proceedings of the AAAI 2001 Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, A. Provetti and S. T. Cao, Eds. AAAI Press, Stanford, CA, 45--52.]]
36. Eiter, T., Faber, W., Leone, N., and Pfeifer, G. 2003a. Computing preferred answer sets by meta-interpretation in answer set programming. Theor. Pract. Logic Programm. 3, 463--498.]]
37. Eiter, T., Faber, W., Leone, N., Pfeifer, G., and Polleres, A. 2000b. Planning under incomplete knowledge. In Proceedings of the First International Conference on Computational Logic (CL 2000), London, UK, J. Lloyd et al., Eds. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 1861. Springer, Berlin, Germany, 807--821.]]
38. Eiter, T., Faber, W., Leone, N., Pfeifer, G., and Polleres, A. 2001b. A logic programming approach to knowledge-state planning: Semantics and complexity. Tech. rep. INFSYS RR-1843-01-11. Institut für Informationssysteme, Technische Universität Wien, Vienna, Austria. To appear in ACM Transactions on Computational Logic.]]
39. Eiter, T., Faber, W., Leone, N., Pfeifer, G., and Polleres, A. 2003b. A logic programming approach to knowledge-state planning, II: The DLVK system. Artificial Intelligence 144, 1--2, 157--211.]]
40. Eiter, T., Faber, W., Leone, N., Pfeifer, G., and Polleres, A. 2002b. Answer set planning under action costs. In Proceedings of the 8th Europ. Conference on Artificial Intelligence (JELIA), S. Flesca, S. Greco, G. Ianni, and N. Leone, Eds. Lecture Notes in Computer Science, vol. 2424, Springer, Berlin, Germany, 186--197.]]
41. Eiter, T., Fink, M., Sabbatini, G., and Tompits, H. 2001d. A framework for declarative update specifications in logic programs. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), B. Nebel, Ed. Morgan Kaufmann, San Francisco, CA, 649--654. See also Tech. rep. INFSYS RR-1843-02-07, TU Wien, Vienna, Austria, 2002.]]
42. Eiter, T., Fink, M., Sabbatini, G., and Tompits, H. 2001e. An update front-end for extended logic programs. In Proceedings of the 6th International Conference on Logic Programm. and Nonmonotonic Reasoning (LPNMR-01), T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in Computer Science, vol. 2173. Springer, Berlin, Germany, 397--401.]]
43. Eiter, T., Fink, M., Sabbatini, G., and Tompits, H. 2002c. On properties of update sequences based on causal rejection. Theor. Pract. Logic Programm. 2, 6, 721--777.]]
44. Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artificial Intelligence 15, 3/4, 289--323.]]
45. Eiter, T., Gottlob, G., and Leone, N. 1997a. Abduction from logic programs: Semantics and complexity. Theoret. Comput. Sci. 189, 1--2 (Dec.), 129--177.]]
46. Eiter, T., Gottlob, G., and Mannila, H. 1997b. Disjunctive datalog. ACM Trans. Database Syst. 22, 3 (Sept.), 364--418.]]
47. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. 1998a. The KR System dlv: Progress report, comparisons and benchmarks. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), A. G. Cohn, L. Schubert, and S. C. Shapiro, Eds. Morgan Kaufmann, San Francisco, CA, 406--417.]]
48. Eiter, T., Leone, N., and Saccà, D. 1997c. On the partial semantics for disjunctive deductive databases. Ann. Math. Artificial Intelligence 19, 1--2 (Apr.), 59--96.]]
49. Eiter, T., Leone, N., and Saccá, D. 1998b. Expressive power and complexity of partial models for disjunctive deductive databases. Theoret. Comput. Sci. 206, 1--2 (Oct.), 181--218.]]
50. Faber, W., Leone, N., Mateis, C., and Pfeifer, G. 1999. Using database optimization techniques for nonmonotonic reasoning. In Proceedings of the 7th International Workshop on Deductive Databases and Logic Programming (DDLP'99), I. O. Committee, Ed. Prolog Association of Japan, Tokyo, Japan, 135--139.]]
51. Faber, W., Leone, N., and Pfeifer, G. 2001. Experimenting with heuristics for answer set programming. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, WA, USA. Morgan Kaufmann, San Francisco, CA, 635--640.]]
52. Faber, W. and Pfeifer, G. 1996. DLV homepage. Go to http://www.dlvsystem.com/.]]
53. Fernández, J. and Minker, J. 1992. Semantics of disjunctive deductive databases. In Proceedings of the 4th International Conference on Database Theory (ICDT-92). 21--50.]]
54. Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proceedings of the Fifth International Conference and Symposium. MIT Press, Cambridge, MA, 1070--1080.]]
55. Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generat. Comput. 9, 365--385.]]
56. Gelfond, M. and Lifschitz, V. 1998. Action languages. Electron. Trans. Artificial Intelligence 2, 3-4, 193--210.]]
57. Gent, I. and Walsh, T. 1999. Beyond NP: The QSAT phase transition. In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI/IAAI 1999), Orlando, Florida, USA. AAAI Press, Stanford, CA/MIT Press, Cambridge, MA, 648--653.]]
58. Giunchiglia, E. and Lifschitz, V. 1998. An action language based on causal explanation: Preliminary report. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI '98). 623--630.]]
59. Gottlob, G. 1994. Complexity and expressive power of disjunctive logic programming. In Proceedings of the International Logic Programming Symposium (ILPS '94), Ithaca, NY, M. Bruynooghe, Ed. MIT Press, Cambridge, MA, 23--42.]]
60. Gottlob, G., Leone, N., and Veith, H. 1999. Succinctness as a source of expression complexity. Ann. Pure Appl. Logic 97, 1--3, 231--260.]]
61. Greco, S. 1999. Optimization of disjunction queries. In Proceedings of the 16th International Conference on Logic Programming (ICLP'99), Las Cruces, New Mexico, USA, D. D. Schreye, Ed. MIT Press, Cambridge, MA, 441--455.]]
62. Janhunen, T., Niemela, I., Simons, P., and You, J.-H. 2000. Partiality and disjunctions in stable model semantics. In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), Breckenridge, Colorado, USA, A. G. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan Kaufmann, San Francisco, CA, 411--419.]]
63. Janhunen, T., Niemelä, I., Seipel, D., Simons, P., and You, J.-H. 2003. Unfolding partiality and disjunctions in stable model semantics. Tech. rep. cs.AI/0303009. Go online to arXiv.org.]]
64. Johnson, D. S. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. Vol. A. Elsevier Science, Amsterdam, The Netherlands. Chapt. 2.]]
65. Knuth, D. E. 1994. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press, New York, NY.]]
66. Koch, C. and Leone, N. 1999. Stable model checking made easy. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99, Stockholm, Sweden, T. Dean, Ed. Morgan Kaufmann, San Francisco, CA, 70--75.]]
67. Koch, C., Leone, N., and Pfeifer, G. 2003. Enhancing disjunctive logic programming systems by SAT checkers. Artificial Intelligence 15, 1--2 (Dec.), 177--212.]]
68. Leone, N., Perri, S., and Scarcello, F. 2001. Improving ASP instantiators by join-ordering methods. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'01), Vienna, Austria, September 2001, T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 2173. Springer, Berlin, Germany.]]
69. Leone, N., Rullo, P., and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics and computation. Inform. Computat. 135, 2 (Jun.), 69--112.]]
70. Lifschitz, V. 1996. Foundations of logic programming. In Principles of Knowledge Representation, G. Brewka, Ed. CSLI Publications, Stanford, CA, 69--127.]]
71. Lifschitz, V. 2002. Answer set programming and plan generation. Artificial Intelligence 138, 39--54.]]
72. Lifschitz, V., Pearce, D., and Valverde, A. 2001. Strongly equivalent logic programs. ACM Trans. Computat. Logic 2, 4, 526--541.]]
73. Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proceedings of the 11th International Conference on Logic Programming (ICLP'94), Santa Margherita Ligure, Italy, P. Van Hentenryck, Ed. MIT Press, Cambridge, MA, 23--37.]]
74. Lin, F. and Zhao, Y. 2002. ASSAT: Computing answer sets of a logic program by SAT solvers. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-2002), Edmonton, Alberta, Canada. AAAI Press, Stanford, CA/MIT Press, Cambridge, MA.]]
75. Lobo, J., Minker, J., and Rajasekar, A. 1992. Foundations of Disjunctive Logic Programming. MIT Press, Cambridge, MA.]]
76. Marek, W. and Truszczyński, M. 1991. Autoepistemic logic. J. Assoc. Comput. Mach. 38, 3, 588--619.]]
77. McCain, N. and Turner, H. 1998. Satisfiability planning with causal theories. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), A. G. Cohn, L. Schubert, and S. C. Shapiro, Eds. Morgan Kaufmann, San Francisco, CA, 212--223.]]
78. Minker, J. 1982. On indefinite data bases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction (CADE '82), D. Loveland, Lecture Notes in Computer Science, vol. 138. Springer, New York, NY, 292--308.]]
79. Minker, J. 1994. Overview of Disjunctive Logic Programming. Ann. Math. Artificial Intelligence 12, 1--24.]]
80. Minker, J. 1996. Logic and databases: A 20 year retrospective. In Proceedings of the International Workshop on Logic in Databases (LID '96). Lecture Notes in Computer Science, vol. 1154. Springer, Berlin, Germany, 3--57.]]
81. Nicolas, P., Saubion, F., and Stéphan, I. 2002. Answer Set Programming by ant colony optimization. In Proceedings of the 8th Europ. Conference on Artificial Intelligence (JELIA), S. Flesca, S. Greco, G. Ianni, and N. Leone, Eds. Lecture Notes in Computer Science, vol. 2424. Springer, Berlin, Germany, 186--197.]]
82. Niemelä, I. and Simons, P. 1997. Smodels---an implementation of the stable model and well-founded semantics for normal logic programs. In Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97), J. Dix, U. Furbach, and A. Nerode, Eds. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 1265. Springer, Berlin, Germany, 420--429.]]
83. Niemelä, I., Simons, P., and Syrjänen, T. 2000. Smodels: A system for Answer Set Programming. In Proceedings of the 8th International Workshop on Non-Monotonic Reasoning (NMR'2000), Breckenridge, Colorado, USA, C. Baral and M. Truszczyński, Eds.]]
84. Papadimitriou, C. H. 1984. The complexity of unique solutions. Assoc. Comput. Mach. 31, 492--500.]]
85. Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA.]]
86. Pearce, D., Sarsakov, V., Schaub, T., Tompits, H., and Woltran, S. 2002. A polynomial translation of logic programs with nested expressions into disjunctive logic programs: Preliminary report. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR'2002), Toulouse, France.]]
87. Pfeifer, G. 2004. Improving the model generation/checking interplay to enhance the evaluation of disjunctive programs. In Proceedings of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR-7), V. Lifschitz and I. Niemelä, Eds. Lecture Notes in Computer Science, vol. 2923. Springer, Berlin, Germany, 220--233.]]
88. Poole, D. 1989. Explanation and prediction: An architecture for default and abductive reasoning. Computat. Intell. 5, 1, 97--110.]]
89. Przymusinski, T. 1990. Stationary semantics for disjunctive logic programs and deductive databases. In Proceedings of the North American Conference on Logic Programming. 40--62.]]
90. Przymusinski, T. 1995. Static semantics for normal and disjunctive logic programs. Ann. Math. Artificial Intelligence 14, 323--357.]]
91. Przymusinski, T. C. 1988. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Morgan Kaufmann, San Francisco, CA, 193--216.]]
92. Przymusinski, T. C. 1991. Stable semantics for disjunctive programs. New Generat. Comp. 9, 401--424.]]
93. Radziszowski, S. P. 1994. Small RAMSEY numbers. Electron. J. Combinatorics 1. Revision 9: July 15, 2002.]]
94. Rao, P., Sagonas, K. F., Swift, T., Warren, D. S., and Freire, J. 1997. XSB: A system for efficiently computing well-founded semantics. In Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'97), J. Dix, U. Furbach, and A. Nerode, Eds. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 1265. Springer, Berlin, Germany, 2--17.]]
95. Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32, 57--95.]]
96. Ross, K. 1990. The well-founded semantics for Disjunctive Logic Programs. In Deductive and Object-Oriented Databases, W. Kim, J.-M. Nicolas, and S. Nishio, Eds. Elsevier Science, Amsterdam, The Netherlands, 385--402.]]
97. Sakama, C. 1989. Possible model semantics for disjunctive databases. In Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD-89). North-Holland, Amsterdam, The Netherlands, 369--383.]]
98. Schaub, T. and Wang, K. 2001. A comparative study of logic programs with preference. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001). Morgan Kaufmann, San Francisco, CA, 597--602.]]
99. Seipel, D. and Thöne, H. 1994. DisLog---A system for reasoning in disjunctive deductive databases. In Proceedings of the International Workshop on the Deductive Approach to Information Systems and Databases (DAISD'94), A. Olivé, Ed. Universitat Politecnica de Catalunya (UPC), Barcelona, Spain, 325--343.]]
100. Simons, P. 2000. Extending and implementing the stable model semantics. Ph.D. dissertation. Helsinki University of Technology, Helsinki, Finland.]]
101. Simons, P., Niemelä, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1--2, 181--234.]]
102. Syrjänen, T. 2002. Lparse 1.0 user's manual. Go online to <URL:http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz>.]]
103. van Gelder, A., Ross, K., and Schlipf, J. 1991. The well-founded semantics for general logic programs. Assoc. Comput. Mach. 38, 3, 620--650.]]
104. Wolfinger, B., Ed. 1994. Workshop: Disjunctive Logic Programming and Disjunctive Databases Proceedings, 13th IFIP World Computer Congress, Hamburg, Germany. German Society for Computer Science (GI) Springer, Berlin, Germany.]]
105. Zhao, Y. 2002. ASSAT homepage. Go online to http://assat.cs.ust.hk/.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Nonmonotonic, default reasoning and belief revision

  • Machine learning

    • Machine learning approaches

      • Rule learning

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

• Theory of computation

  • Formal languages and automata theory