The Valid Model Semantics for Logic Programs.

@inproceedings{DBLP:conf/pods/BeeriRSS92,
  author    = {Catriel Beeri and
               Raghu Ramakrishnan and
               Divesh Srivastava and
               S. Sudarshan},
  title     = {The Valid Model Semantics for Logic Programs},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {91-104},
  ee        = {http://doi.acm.org/10.1145/137097.137115, db/conf/pods/BeeriRSS92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present the valid model semantics, a new approach to providing semantics for logic programs with negation, set-terms and grouping. The valid model semantics is a three-valued semantics, and is defined in terms of a 'normal form' computation. The valid model semantics also gives meaning to the generation and use of non-ground facts (i.e., facts with variables) in a computation.

The formulation of the semantics in terms of a normal form computation offers important insight not only into the valid model semantics, but also into other semantics proposed earlier. We show that the valid model semantics extends the well-founded semantics in a natural manner, and has several advantages over it. The well-founded semantics can also be understood using a variant of the normal form computations that we use; the normal form computations used for valid semantics seem more natural than those used for well-founded semantics.

We also show that the valid model semantics has several other desirable properties: it is founded ([SZ90]), it is contained in every regular model ([YY90]), and it is contained in every two-valued stable model.

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

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

• 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

Online Edition: ACM Digital Library

References

[ABW88]

...

[BNST91]

Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. J. Log. Program. 10(1/2/3&4): 181-232(1991) BibTeX

[BRSS91]

...

[GGZ91]

Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163 BibTeX

[GL88]

Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX

[KS91]

David B. Kemp, Peter J. Stuckey: Semantics of Logic Programs with Aggregates. ISLP 1991: 387-401 BibTeX

[PP88]

Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 BibTeX

[Prz88]

...

[Prz90]

Teodor C. Przymusinski: Extended Stable Semantics for Normal and Disjunctive Programs. ICLP 1990: 459-477 BibTeX

[Prz91]

Teodor C. Przymusinski: Semantics of Disjunctive Logic Programs and Deductive Databases. DOOD 1991: 85-107 BibTeX

[Ros90]

Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171 BibTeX

[RS91]

...

[Sch]

...

[SZ90]

Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX

[Van89]

Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX

[Van92]

Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138 BibTeX

[VRS91]

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

[YY90]

Jia-Huai You, Li-Yan Yuan: Three-Valued Formalization of Logic Programming: Is It Needed? PODS 1990: 172-182 BibTeX

Referenced by

1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
2. Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
3. Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138
4. Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15