dblp.uni-trier.de www.dagstuhl.de www.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},
  editor    = {Chris Edmondson-Yurkanan and
               Mihalis Yannakakis},
  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, USA},
  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}
}

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 ...

Printed Edition

Chris Edmondson-Yurkanan, Mihalis Yannakakis (Eds.): Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas, USA. ACM 1988, ISBN 0-89791-263-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Last update Fri Sep 14 17:28:27 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page