The expressive powers of the logic programming semantics (extended abstract)

ABSTRACT

We compare the expressive powers of three semantics for deductive databases and logic programming: the 3-valued program completion semantics, the well-founded semantics, and the stable semantics, We identify the expressive power of the stable semantics, and in fairly general circumstances that of the well-founded semantics. Over infinite Herbrand models, where the three semantics have equivalent expressive power, we also consider a notion of uniform translatability between the 3-valued program completion and well-founded semantics. In this sense of uniform translatability we show the well-founded semantics to be more expressive.

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
• Acz77: P. Aczel. An introduction to inductive definitions, In J. Barwise, editor, Handbook of Mathematical Logic, pages 739-782, North- Holland, New York, 1977.
• AU79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• Bar75: J. Barwise. Admissible Sets and Structures. Springer-Verlag, New York, 1975.
• Bry89: F. Bry, Logic programming as constructivism: a formalization and its application to databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-50, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73725]
• BS76: J. Barwise and J. Schlipf An introduction to recursively saturated and resplendent models. Journal of Symbolic Logic, 41(2): 531-536, 1976.
• CH82: Ashok Chandra and David Harel. Structure and complexity of relational queries. JCSS, 25(1):99-128, 1982.
• CH85: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• Cla78: K.L. Clark. Negation as failure. In Gallaire and Minker, editors, Logic and Databases, pages 293-322, Plenum Press, New York, 1978.
• Fa74: R. Fagin Generalized first-order spectra and polynomial-time recognizable sets. In Karp, editor, Complexity of Computation, pages 43-74, American Mathematical Society, Providence, Rhode Island, 1974.
• Fit85: M. Fitting. A Kripke-Kleene semantics for logic programs. Journal of Logic Programming, 2(4):295-312, 1985.
• Gel87: M. Gelfond. On stratified autoepistemic theories. In Proc. AAAI, 1987.
• GL88: M:. Gelfond and V. Lifschitz The stable model semantics for logic programming. In Proc. 5th In t'l Conf. Syrup. on Logic Programming, 1988.
• GS86: Y. Gurevich and S. Shelah. Fixed-point extensions of first order logic. Annals of Pure and Applied Logic, 32:265-280, 1986.
• Imm86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• Kun87: Kenneth Kunen, Negation in logic programming, Journal of Logic Programming, v.4 n.4, p.289-308, December 1, 1987 [doi>10.1016/0743-1066(87)90007-0]
• Kun88: K. Kunen. Some remarks on the completed database. Technical Report 775, Univ. of Wisconsin, Madison, WI 53706.
• Lif88: V. Lifschitz, On the declarative semantics of logic programs with negation, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• MT88: W. Marek and M. Truszczynski Autoepistemic Logic Technical Report, University of Kentucky.
• Mos74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• 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
• Prz89: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• Ros89: K. A. Ross, A procedural semantics for well founded negation in logic programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.22-33, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73724]
• Sch78: j. Schlipf Toward model theory through recursive saturation. J. Symbolic Logic 43, pages 183-206, 1978.
• She85: John C. Shepherdson, Negation as failure. II, Journal of Logic Programming, v.2 n.3, p.185-202, Oct. 1985 [doi>10.1016/0743-1066(85)90018-4]
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• VEK76: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• VG86: A. Van Gelder. Negation as failure using tight derivations for general logic programs. In Proc. Third IEEE Symposium on Logic Programming, Salt Lake City, Utah, Springer-Verlag, New York, 1986.
• VG89: 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]
• VGRS88: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]

INDEX TERMS

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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming; Deduction (e.g., natural, rule-based)

General Terms:
Design, Languages, Management, Performance, Theory, Verification