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}
}
BibTeX
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 ...
BibTeX
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 BibTeX
References
- [AV]
- Serge Abiteboul, Victor Vianu:
Fixpoint Extensions of First-Order Logic and Datalog-Like Languages.
LICS 1989: 71-79 BibTeX
- [ABW]
- ...
- [CH]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985) BibTeX
- [GL]
- Michael Gelfond, Vladimir Lifschitz:
The Stable Model Semantics for Logic Programming.
ICLP/SLP 1988: 1070-1080 BibTeX
- [KN]
- Ravi Krishnamurthy, Shamim A. Naqvi:
Non-Deterministic Choice in Datalog.
JCDKB 1988: 416-424 BibTeX
- [KP]
- Phokion G. Kolaitis, Christos H. Papadimitriou:
Why Not Negation by Fixpoint?
PODS 1988: 231-239 BibTeX
- [L]
- John W. Lloyd:
Foundations of Logic Programming, 2nd Edition.
Springer 1987, ISBN 3-540-18199-7
BibTeX
- [N]
- ...
- [NT]
- Shamim A. Naqvi, Shalom Tsur:
A Logical Language for Data and Knowledge Bases.
Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
- [P1]
- ...
- [P2]
- ...
- [P3]
- Teodor C. Przymusinski:
Perfect Model Semantics.
ICLP/SLP 1988: 1081-1096 BibTeX
- [P4]
- Teodor C. Przymusinski:
Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model.
PODS 1989: 11-21 BibTeX
- [P5]
- ...
- [PP]
- Halina Przymusinska, Teodor C. Przymusinski:
Weakly Perfect Model Semantics for Logic Programs.
ICLP/SLP 1988: 1106-1120 BibTeX
- [R]
- Kenneth A. Ross:
A Procedural Semantics for Well Founded Negation in Logic Programs.
PODS 1989: 22-33 BibTeX
- [SZ]
- ...
- [U1]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
- [U2]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
- [V1]
- Allen Van Gelder:
Negation as Failure Using Tight Derivations for General Logic Programs.
SLP 1986: 127-138 BibTeX
- [V2]
- Allen Van Gelder:
The Alternating Fixpoint of Logic Programs with Negation.
PODS 1989: 1-10 BibTeX
- [VRS]
- Allen Van Gelder, Kenneth A. Ross, John S. Schlipf:
Unfounded Sets and Well-Founded Semantics for General Logic Programs.
PODS 1988: 221-230 BibTeX
- [Z]
- Carlo Zaniolo:
Object Identity and Inheritance in Deductive Databases - an Evolutionary Approach.
DOOD 1989: 7-21 BibTeX
Referenced by
- Li-Yan Yuan, Jia-Huai You:
Coherence Approach to Logic Program Revision.
IEEE Trans. Knowl. Data Eng. 10(1): 108-119(1998)
- Thomas Eiter, Georg Gottlob, Heikki Mannila:
Disjunctive Datalog.
ACM Trans. Database Syst. 22(3): 364-418(1997)
- Marco Cadoli, Thomas Eiter, Georg Gottlob:
Default Logic as a Query Language.
IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
- 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)
- V. S. Subrahmanian, Dana S. Nau, Carlo Vago:
WFS + Branch and Bound = Stable Models.
IEEE Trans. Knowl. Data Eng. 7(3): 362-377(1995)
- Jan Paredaens, Peter Peelman, Letizia Tanca:
G-Log: A Graph-Based Query Language.
IEEE Trans. Knowl. Data Eng. 7(3): 436-453(1995)
- Domenico Saccà:
Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries.
ICDT 1995: 353-367
- Sergio Greco, Domenico Saccà, Carlo Zaniolo:
DATALOG Queries with Stratified Negation and Choice: from P to DP.
ICDT 1995: 82-96
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Marco Schaerf:
Negation and Minimality in Non-Horn Databases.
PODS 1993: 147-157
- Anthony J. Bonner, Michael Kifer, Mariano P. Consens:
Database Programming in Transaction Logic.
DBPL 1993: 309-337
- Sergio Greco, Carlo Zaniolo, Sumit Ganguly:
Greedy by Choice.
PODS 1992: 105-113
- Jan Van den Bussche, Dirk Van Gucht:
Semi-determinism.
PODS 1992: 191-201
- Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan:
The Valid Model Semantics for Logic Programs.
PODS 1992: 91-104
- Serge Abiteboul, Allen Van Gelder:
Optimizing Active Databases using the Split Technique.
ICDT 1992: 171-187
- Yeh-Heng Sheng:
A Non-deterministic Deductive Database Language.
SIGMOD Conference 1991: 188-197
- Sumit Ganguly, Sergio Greco, Carlo Zaniolo:
Minimum and Maximum Predicates in Logic Programming.
PODS 1991: 154-163
- Els Laenens, Dirk Vermeir:
On the Relationship between Well-Founded and Stable Partial Models.
MFDBS 1991: 59-73
- Filippo Cacace, Stefano Ceri, Letizia Tanca:
Consistency and Non-determinism in a Database Programming Language.
MFDBS 1991: 325-341
- Els Laenens, Domenico Saccà, Dirk Vermeir:
Extending Logic Programming.
SIGMOD Conference 1990: 184-193
- Carlo Zaniolo:
Deductive Databases - Theory Meets Practice.
EDBT 1990: 1-15
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:34:00 2009