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

Stable Models and Non-Determinism in Logic Programs with Negation.

Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217
@inproceedings{DBLP:conf/pods/SaccaZ90,
  author    = {Domenico Sacc{\`a} and
               Carlo Zaniolo},
  title     = {Stable Models and Non-Determinism in Logic Programs with Negation},
  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     = {205-217},
  ee        = {http://doi.acm.org/10.1145/298514.298572, db/conf/pods/SaccaZ90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Previous researchers have proposed generalizations of Horn clause logic to support negation and nondeterminism as two separate extensions. In this paper, we show that the stable model semantics for logic programs provides a unified basis for the treatment of both concepts. First, we introduce the concepts of partial models, stable models, strongly founded models and deterministic models and other interesting classes of partial models and study their relationships. We show that the maximal deterministic model of a program is a subset of the intersection of all its stable models and that the well-founded model of a program is a subset of its maximal deterministic model. Then, we show that the use of stable models subsumes the use of the non-deterministic choice construct in LDL and provides an alternative definition of the semantics of this construct. Finally, we provide a constructive definition for stable models with the introduction of a procedure, called backtracking fixpoint, that nondeterministically constructs a total stable model, if such a model exists.

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.


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

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[AV]
Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ABW]
...
[CH]
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
[GL]
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
[KN]
Ravi Krishnamurthy, Shamim A. Naqvi: Non-Deterministic Choice in Datalog. JCDKB 1988: 416-424 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KP]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[L]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[N]
...
[NT]
Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[P1]
...
[P2]
...
[P3]
Teodor C. Przymusinski: Perfect Model Semantics. ICLP/SLP 1988: 1081-1096 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[P4]
Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[P5]
...
[PP]
Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[R]
Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SZ]
...
[U1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[U2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[V1]
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
[V2]
Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VRS]
Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Z]
Carlo Zaniolo: Object Identity and Inheritance in Deductive Databases - an Evolutionary Approach. DOOD 1989: 7-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:51:34 2010 by Michael Ley (ley@uni-trier.de)