Colin Bell
Abstract
Though the declarative semantics of both explicit and nonmonotonic negation in logic programs has been studied extensively, relatively little work has been done on computation and implementation of these semantics. In this paper, we study three different approaches to computing stable models of logic programs based on mixed integer linear programming methods for automated deduction introduced by R. Jeroslow. We subsequently discuss the relative efficiency of these algorithms. The results of experiments with a prototype compiler implemented by us tend to confirm our theoretical discussion. In contrast to resolution, the mixed integer programming methodology is both fully declarative and handles reuse of old computations gracefully.
We also introduce, compare, implement, and experiment with linear constraints corresponding to four semantics for “explicit” negation in logic programs: the four-valued annotated semantics [Blair and Subrahmanian 1989], the Gelfond-Lifschitz semantics [1990], the over-determined models [Grant and Subrahmanian 1989], the Gelfond-Lifschitz semantics [1990], the over-determined models [Grant and Subrahmanian 1990], and the classical logic semantics. Gelfond and Lifschitz[1990] argue for simultaneous use of two modes of negation in logic programs, “classical” and “nonmonotonic,” so we give algorithms for computing “answer sets” for such logic programs too.
- ~BELL, C., NERODE, A., NO, R., AND SUBRAHMANIa, N, V S. 1992. Implementing deductive ~databases by linear programming. In Proceedblgs of the l lth ACM SIG,4CT-SIGMOD-SIG~4RT ~Symposium on Principles of Database &'stems (San Diego, Calif., June 2-4). ACM, New York, ~pp. 283-292. (Currently available as Tech. Rep. CS-TR-2747. Univ. Maryland, College Park, ~Md., (Aug.) 1991.) Google Scholar
- ~BLAIR, C., JEROSLOW, R G., AND LOWE, J. K. 1988. Some results and experiments m program- ~ming techniques for propositional logic. Cottz{;tit. Op. Re5 13, 633 645. Google Scholar
- ~BLAIR, H. A., AND SUBRAHMANIAN, V. S. 1989. Paraconsistent logic programming. Theoret. ~Comput. Set. 6& 135 154. Google Scholar
- ~CUADRADO, J., AND PiMENTEL, S. 1989. A truth maintenance system based on stable models. In ~Proceedbzgs of the 1989 North American Conference on Logic Programming, MIT Press, Cam- ~bridge, Mass. pp. 274-290.Google Scholar
- ~DOWLING, W., AND GALLIER, J. 1984. Linear-time algorithms for testing the satlsfiabdlty of ~propositional horn theories. J. Logic Prog. 3, 267 284.Google Scholar
- ~FERNANDEZ, J., LOBO, J., MINKER, J., AND SUBRAHMANIAN, V. S. 1993. Disjunctive LP + Integrity ~constraints - Stable model semantics. ,4n~l. Math. Artlf. Int. 18, 449 479.Google Scholar
- ~FUENI'ES, L. O. 1991. Applying uncertainty formalisms to well-defined problems, manuscriptGoogle Scholar
- ~GELFOND, M., AND LIFSCH1TZ, V 1988. The stable model semantics for logic programming. In ~Proceedings of the 5th InternattorzaI Conference and Symposzum on Logtc Programming (R. A. ~Kowalski and K. A. Bowen, ed.). pp. 1070-1080.Google Scholar
- ~(3ELFOND, M., AND LIFSCHITZ, V. 1990. Logic programs with classical negation. In Proceedings of ~the 7th Internattonal Conference and &,rnposiztm on Logic Programming (D. H. D. Warren and ~P. Szeredl, eds.), pp. 579-597. Google Scholar
- ~GILLET, B. E. 1976. Introduction to Operations Research: ~4 Comp,ter-Ortentcd Algorithmtc ~Approach. McGraw-Hill, New York.Google Scholar
- ~GOMORY, R. E. 1963. An algorithm for integer solutions to hnear programs. In Rece~ztAdt'aHce,s ~m Mathematical Programming (R. Graves and P. Wolfe, eds.). McGraw-Hill, New York.Google Scholar
- ~GRANT, J., AND SUBRAHMANIAN, g. S. 1990. Reasoning about inconsistent knowledge bases. ~IEEE Tra~zs. Ktzow. Data Eng., to appear. (Currently available as Tech. Rep. CS-TR-2532. Unw. ~Maryland, College Park, Md.) Google Scholar
- ~H1LL1ER, F., AND LIEBERMAN, G. i986. ltztrodttetton to Operations Researrh, 4th ed Holden-Day, ~Oakland, Cahf. Google Scholar
- ~HOOKER, J. 1988. A quantitative approach to logical inference. Dec. Supp. Syst. 4, 45-69. Google Scholar
- ~HOOKER, J., AND FEDJK1, C. 1990. Branch-and-cut solution of inference problems in proposi- ~tional logic. Ann. Math. Artif Int., 123-139.Google Scholar
- ~JAFFAR, J., AND LASSEZ, J. L. 1987. Constraint logic programming. In Proceedings of the 14th ~Annual Symposium on Principles of Programming Languages. (Munich, West Germany, Jan. ~21-23). ACM, New York, pp. 111-119. Google Scholar
- ~JEROSLOW, R. E. 1988. Computation-oriented reductions of predicate to propositional logic. ~Dec. Supp. Syst. 4, 183-187. Google Scholar
- ~JEROSLOW, R. E. 1989. Logic-based Decision Support: Mixed Integer Model Formulation. North- ~Holland, Amsterdam, The Netherlands.Google Scholar
- ~KAGAN, V., NERODE, A., AND SUBRAHMANIAN, V. S. 1993. Computing definite logic programs by ~partial instantiation. Math. Sciences Inst. TR-93-24. Cornell Univ., Ithaca, N.Y., May.Google Scholar
- ~KAGAN, V., NERODE, A., AND SUBRAHMANIAN, V. S. 1994. Computing minimal models by partial ~instantiation. Theoret. Conzpttt. Sci., to appear. Google Scholar
- ~KHACmAN, L. G. 1979. A polynomial algorithm for linear programming. Doklady Akad. Nauk ~USSR 224, 1093-1096. (Translated in Soviet Math Doklady 20, 191-194.)Google Scholar
- ~LLOYD, J. W. 1987. Foundations of Logic Programming. Springer-Verlag, New York. Google Scholar
- ~LOBO, J., MINKER, J., AND RAJASEKAR, A. 1992. Foundations of Disjuncttt,e Logic' Programming, ~MIT Press, Cambridge, Mass. Google Scholar
- ~MAREK, W., NERODE, A., AND REMMEL, J. 1991. A theory of nonmonotonic rule systems, I. Ann. ~Math. Arti. hzt. 1,241-273.Google Scholar
- ~MAREK, W., AND SUBRAHMANIAN, g. S. 1992. The relationship between stable, supported, ~default and auto-epistemic semantics for general logic programs. Theoret. Comput. Sct. 103, ~365-386. Google Scholar
- ~MINKER, J. 1982. On indefinite databases and the closed world assumption. In Proceedings of the ~6th Con)'~rence on Automated Deduction, (D. Loveland, ed.). Lecture Notes in Computer ~Science, vol. 138. Springer-Verlag, New York, pp. 292-308. Google Scholar
- ~MURAT& T., SUBRAHMANIAN, V. S., AND WAKAYAMA, T. 1991. A petri net model for reasoning ~in the presence of inconsistency. IEEE Trans. Knowl. Data Eng. 3, 3, 281-292. Google Scholar
- ~NEMHAUSER, G., AND WOLSEY, L. 1988. Integer and Combinatorial Optimization. Wiley, New ~York. Google Scholar
- ~PENG, Y., AND REGGIA, J. 1989. A connectionist model for diagnostic problem solving. IEEE ~Trans. Syst., Man and Cyber. 19, 2, 285-298.Google Scholar
- ~SUBRAHMANIAN, V. S., NAU, D. S., AND VAGO, C. 1994. WFS + Branch and Bound = Stable ~Models. IEEE Trans. Knowl. and Data Eng., to appear. Google Scholar
- ~ULLMAN, J. D. 1988. Principles of Database and Knowledge-Base System. Vol. 1. Computer ~Science Press, Baltimore, Md. Google Scholar
- ~VAN GELDER, A. 1989. The alternating fixpoint of logic programs with negation. In Proceedings ~of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems ~(Philadelphia, Pa., Mar. 29-3t). ACM. New York, pp. 1 10. Google Scholar
Index Terms
- Mixed integer programming methods for computing nonmonotonic deductive databases
Recommendations
‘Classical’ Negation in Nonmonotonic Reasoning and Logic Programming
Gelfond and Lifschitz were the first to point out the need for a symmetric negation in logic programming and they also proposed a specific semantics for such negation for logic programs with the stable semantics, which they called ‘classical’. Subsequently,...
Ground Nonmonotonic Modal Logic S5: New Results
We study logic programs under Gelfond's translation in the context of modal logic S5. We show that for arbitrary logic programs (propositional theories where logic negation is associated with default negation) ground nonmonotonic modal logics between T ...
Nonmonotonic Logic Programming
This paper provides a survey of the state of the art in nonmonotonic logic programming. In particular, we survey advances in the declarative semantics of logic programs, in query processing procedures for nonmonotonic logic programs, and in recent ...
Comments