The Expressive Powers of the Logic Programming Semantics.

@inproceedings{DBLP:conf/pods/Schlipf90,
  author    = {John S. Schlipf},
  title     = {The Expressive Powers of the Logic Programming Semantics},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {196-204},
  ee        = {http://doi.acm.org/10.1145/298514.298564, db/conf/pods/Schlipf90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Journal Version

Online Edition: ACM Digital Library

References

[ABW88]

...

[Acz77]

...

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[Bar75]

...

[Bry89]

François Bry: Logic Programming as Constructivism: A Formalization and its Application to Databases. PODS 1989: 34-50 BibTeX

[BS76]

...

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[Cla78]

...

[Fa74]

...

[Fit85]

Melvin Fitting: A Kripke-Kleene Semantics for Logic Programs. J. Log. Program. 2(4): 295-312(1985) BibTeX

[Gel87]

Michael Gelfond: On Stratified Autoepistemic Theories. AAAI 1987: 207-211 BibTeX

[GL88]

Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX

[GS86]

...

[Imm86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Kun87]

Kenneth Kunen: Negation in Logic Programming. J. Log. Program. 4(4): 289-308(1987) BibTeX

[Kun88]

...

[Lif88]

...

[MT88]

...

[Mos74]

...

[Prz88]

...

[Prz89]

Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX

[Ros89]

Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 BibTeX

[Sch78]

...

[She85]

John C. Shepherdson: Negation as Failure II. J. Log. Program. 2(3): 185-202(1985) BibTeX

[Var82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[VEK76]

Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

[VG86]

Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX

[VG89]

Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX

[VGRS88]

Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230 BibTeX

Referenced by

1. Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
2. Weidong Chen, David Scott Warren: Computation of Stable Models and Its Integration with Logical Query Processing. IEEE Trans. Knowl. Data Eng. 8(5): 742-757(1996)
3. Domenico Saccà: Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries. ICDT 1995: 353-367
4. Sergio Greco, Domenico Saccà, Carlo Zaniolo: DATALOG Queries with Stratified Negation and Choice: from P to D^P. ICDT 1995: 82-96