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

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

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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

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

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
[ABW]: ...
[CH]: Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985)
[GL]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080
[KN]: Ravi Krishnamurthy, Shamim A. Naqvi: Non-Deterministic Choice in Datalog. JCDKB 1988: 416-424
[KP]: Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239
[L]: John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
[N]: ...
[NT]: Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
[P1]: ...
[P2]: ...
[P3]: Teodor C. Przymusinski: Perfect Model Semantics. ICLP/SLP 1988: 1081-1096
[P4]: Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21
[P5]: ...
[PP]: Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120
[R]: Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33
[SZ]: ...
[U1]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[U2]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[V1]: Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138
[V2]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10
[VRS]: Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230
[Z]: Carlo Zaniolo: Object Identity and Inheritance in Deductive Databases - an Evolutionary Approach. DOOD 1989: 7-21