The valid model semantics for logic programs

ABSTRACT

We present the valid model semantics, a new approach to providing semantics for logic programs with negation, set-terms and grouping. The valid model semantics is a three-valued semantics, and is defined in terms of a ‘normal form’ computation. The valid model semantics also gives meaning to the generation and use of non-ground facts (i.e., facts with variables) in a computation. The formulation of the semantics in terms of a normal form computation offers important insight not only into the valid model semantics, but also into other semantics proposed earlier. We show that the valid model semantics extends the well-founded semantics in a natural manner, and has several advantages over it. The well-founded semantics can also be undertood using a variant of the normal form computations that we use; the normal form computations used for valid semantics seem more natural than those used for well-founded semantics. We also show that the valid model semantics has several other desirable properties: it is founded ([SZ90]), it is contained in every regular model ([YY90]), and it is contained in every two-valued stable model.

REFERENCES

• ABW88: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• BNST91: Catriel Beeri , Shamim Naqvi , Oded Shmueli , Shalom Tsur, Set constructors in a logic database language, Journal of Logic Programming, v.10 n.3-4, p.181-232, April/May 1991 [doi>10.1016/0743-1066(91)90036-O]
• BRSS91: C. Beeri, P#. Ramakrishnan, D. Srivastava, and S. Sudarshan. Valid computations and the Magic implementation of stratified programs. Manuscript, September 91.
• GGZ91: Sumit Ganguly , Sergio Greco , Carlo Zaniolo, Minimum and maximum predicates in logic programming, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-163, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113427]
• GL88: M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. Fzflh International Conference and Symposzum on Logic Programming, 1988.
• KS91: David Kemp and Peter Stuckey. Semantics of logic programs with aggregates. In Proceedzngs of the International Logic Programmzng Symposium, pages 387-401, Slan Diego, CA, U.S.A., October 1991.
• PP88: H. Przymusinska and T.C. Przymusinski. Weakly perfect model semantics for logic programs. In Proceedings of the Fifth Inlernational Conference/Symposzum on Logic Programming, 1988.
• Prz88: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Prz90: Teodor C. Przymusinski, Extended stable semantics for normal and disjunctive programs, Logic programming, MIT Press, Cambridge, MA, 1990
• Prz91: T. C. Przymusinski. Semantics of disjunctive logic programs and deductive databases. In C. Delobel, M. Kifer, and Y. Masunaga, editors, Proceedings of the Second International Conference on Deductive and Object-Oriented Databases DOOD'81, pages 85-107, Munich, Germany, 1991. Springer-Verlag.
• Ros90: Kenneth A. Ross, Modular stratification and magic sets for DATALOG programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298558]
• RS91: Kenneth Ross and Yehoshua Sagiv. Monotonic aggregation in deductive databases. In Proceedings of the post-ILPS'91 Workshop on Deductive Databases, 1991.
• Sch: John S. Schlipf. Formalizing a logic for logic programming. Annals of Mathematzcs and Artzfic#al lntelhgence. To appear.
• SZ90: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• Van89: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• Van92: Allen Van Gelder, The well-founded semantics of aggregation, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.127-138, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137854]
• VRS91: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• YY90: Jia-Huai You , Li Yan Yuan, Three-valued formalization of logic programming: is it needed?, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-182, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298559]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Languages, Verification