ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Unfounded Sets and Well-Founded Semantics for General Logic Programs.

Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230
@inproceedings{DBLP:conf/pods/GelderRS88,
  author    = {Allen Van Gelder and
               Kenneth A. Ross and
               John S. Schlipf},
  title     = {Unfounded Sets and Well-Founded Semantics for General Logic Programs},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {221-230},
  ee        = {http://doi.acm.org/10.1145/308386.308444, db/conf/pods/GelderRS88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A general logic program (abbreviated to "program hereafter) is a set of rules that have both positive and negative subgoals. It is common to view a deductive database as a general logic program consisting of rules (IDB) sitting above elementary relations (EDB, facts). It is desirable to associate one Herbrand model with a program and think of that model as the "meaning of the program," or its "declarative semantics." Ideally, queries directed to the program would be answered in accordance with this model. We introduce unfounded sets and well-founded partial models, and define the well-founded semantics of a program to be its well- founded partial model. If the well-founded partial model is in fact a model, we call it the well-founded model, and say the program is "well-behaved". We show that the class of well-behaved programs properly includes previously studied classes of "stratified" and "locally stratified" programs. Gelfond and Lifschitz have proposed a definition of "unique stable model" for general logic programs. We show that a program has a unique stable model if it has a well-founded model, in which case they are the same. We discuss why the converse is not true.

Copyright © 1988 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991) BibTeX

References

[ABW86]
...
[AVE82]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
[CH85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[Cla78]
...
[Fit85]
Melvin Fitting: A Kripke-Kleene Semantics for Logic Programs. J. Log. Program. 2(4): 295-312(1985) BibTeX
[GL87]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[HM86]
Steve Hanks, Drew V. McDermott: Default Reasoning, Nonmonotonic Logics, and the Frame Problem. AAAI 1986: 328-333 BibTeX
[JLL83]
Joxan Jaffar, Jean-Louis Lassez, John W. Lloyd: Completeness of the Negation as Failure Rule. IJCAI 1983: 500-506 BibTeX
[Kun87]
Kenneth Kunen: Negation in Logic Programming. J. Log. Program. 4(4): 289-308(1987) BibTeX
[Lif86]
...
[Llo84]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX
[Prz86]
...
[RT87]
Kenneth A. Ross, Rodney W. Topor: Inferring Negative Information from Disjunctive Databases. J. Autom. Reasoning 4(4): 397-424(1988) BibTeX
[Sch87]
...
[She85]
John C. Shepherdson: Negation as Failure II. J. Log. Program. 2(3): 185-202(1985) BibTeX
[She86]
...
[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
[VG88]
Allen Van Gelder: Modeling Simultaneous Events with Default Reasoning and Tight Derivations. J. Log. Program. 8(1): 41-52(1990) BibTeX

Referenced by

  1. Nicola Leone, Pasquale Rullo, Antonella Mecchia, Giuseppe Rossi: A Deductive Environment for Dealing with Objects and Nonmonotonic Reasoning. IEEE Trans. Knowl. Data Eng. 9(4): 539-558(1997)
  2. Jörg Flum, Max Kubierschky, Bertram Ludäscher: Total and Partial Well-Founded Datalog Coincide. ICDT 1997: 113-124
  3. Serge Abiteboul, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275
  4. James J. Lu, Anil Nerode, V. S. Subrahmanian: Hybrid Knowledge Bases. IEEE Trans. Knowl. Data Eng. 8(5): 773-785(1996)
  5. V. S. Subrahmanian, Dana S. Nau, Carlo Vago: WFS + Branch and Bound = Stable Models. IEEE Trans. Knowl. Data Eng. 7(3): 362-377(1995)
  6. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  7. V. S. Subrahmanian: Amalgamating Knowledge Bases. ACM Trans. Database Syst. 19(2): 291-331(1994)
  8. Liwu Li: High-Level Petri Net Model of Logic Program with Negation. IEEE Trans. Knowl. Data Eng. 6(3): 382-395(1994)
  9. Terry Gaasterland, Jorge Lobo: Qualified Answers That Reflect User Needs and Preferences. VLDB 1994: 309-320
  10. Edward P. F. Chan: A Possible World Semantics for Disjunctive Databases. IEEE Trans. Knowl. Data Eng. 5(2): 282-292(1993)
  11. Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
  12. Françoise Gire: Well Founded Semantics and Stable Semantics of Semi-Strict Programs. ICDT 1992: 261-275
  13. José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50
  14. Gerd Wagner: A Database Needs Two Kinds of Negation. MFDBS 1991: 357-371
  15. Els Laenens, Dirk Vermeir: On the Relationship between Well-Founded and Stable Partial Models. MFDBS 1991: 59-73
  16. Els Laenens, Domenico Saccà, Dirk Vermeir: Extending Logic Programming. SIGMOD Conference 1990: 184-193
  17. Jia-Huai You, Li-Yan Yuan: Three-Valued Formalization of Logic Programming: Is It Needed? PODS 1990: 172-182
  18. John S. Schlipf: The Expressive Powers of the Logic Programming Semantics. PODS 1990: 196-204
  19. Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217
  20. Hervé Gallaire, Jean-Marie Nicolas: Logic and Databases: An Assessment. ICDT 1990: 177-186
  21. Nicole Bidoit, P. Legay: WELL!: An Evaluation Procedure for All Logic Programs. ICDT 1990: 335-348
  22. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  23. Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33
  24. Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21
  25. Michael Kifer, James Wu: A Logic for Object-Oriented Logic Programming (Maier's O-Logic Revisited). PODS 1989: 379-393
  26. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:54 2009