The Alternating Fixpoint of Logic Programs with Negation.

@inproceedings{DBLP:conf/pods/Gelder89,
  author    = {Allen Van Gelder},
  title     = {The Alternating Fixpoint of Logic Programs with Negation},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {1-10},
  ee        = {http://doi.acm.org/10.1145/73721.73722, db/conf/pods/Gelder89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We introduce and describe the alternating fixpoint of a logic program with negation. The underlying idea is to monotonically build up a set of negative conclusions until the least fixpoint is reached, using a transformation related to the one that defines stable models, developed by Gelfond and Lifschitz. From a fixed set of negative conclusions, we can derive the positive conclusions that follow (without deriving any further negative ones), by traditional Horn clause semantics. The union of positive and negative conclusions is called the alternating fixpoint partial model. The name "alternating" was chosen because the transformation runs in two passes; the first pass transforms an underestimate of the set of negative conclusions into an (intermediate) overestimate; the second pass transforms the overestimate into a new underestimate; the composition of the two passes is monotonic.

Our main theorem is that the alternating fixpoint partial model is exactly the well-founded partial model.

We also show that a system in fixpoint logic, which permits rule bodies to be first order formulas but requires inductive relations to be positive within them, can be transformed straightforwardly into a normal logic program whose alternating fixpoint partial model corresponds to the least fixpoint of the fixpoint logic system. Thus alternating fixpoint logic is at least as expressive as fixpoint logic. The converse is shown to hold for finite structures.

Copyright © 1989 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]

...

[Acz77]

...

[AV88]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[Cho88]

...

[Cla78]

...

[FB88]

Melvin Fitting, Marion Ben-Jacob: Stratified and Three-valued Logic Programming Semantics. ICLP/SLP 1988: 1054-1069 BibTeX

[Fit85]

Melvin Fitting: A Kripke-Kleene Semantics for Logic Programs. J. Log. Program. 2(4): 295-312(1985) BibTeX

[Gel87]

Michael Gelfond: On Stratified Autoepistemic Theories. AAAI 1987: 207-211 BibTeX

[GL88]

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

[GS86]

...

[Imm86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Kol87]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX

[Kun87]

Kenneth Kunen: Negation in Logic Programming. J. Log. Program. 4(4): 289-308(1987) BibTeX

[Kun88]

Kenneth Kunen: Some Remarks on the Completed Database. ICLP/SLP 1988: 978-992 BibTeX

[Lif88]

...

[Llo87]

John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX

[LT84]

John W. Lloyd, Rodney W. Topor: Making Prolog more Expressive. J. Log. Program. 1(3): 225-240(1984) BibTeX

[MT88]

...

[PP88]

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

[Prz88]

...

[Prz89]

Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX

[Rei78]

...

[Ros89]

Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 BibTeX

[Sch88]

...

[She85]

John C. Shepherdson: Negation as Failure II. J. Log. Program. 2(3): 185-202(1985) BibTeX

[She88]

...

[VG86]

Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX

[VG88]

...

[VGRS88]

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

Referenced by

1. Li-Yan Yuan, Jia-Huai You: Coherence Approach to Logic Program Revision. IEEE Trans. Knowl. Data Eng. 10(1): 108-119(1998)
2. Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
3. Sushil Jajodia, Pierangela Samarati, V. S. Subrahmanian, Elisa Bertino: A Unified Framework for Enforcing Multiple Access Control Policies. SIGMOD Conference 1997: 474-485
4. Jörg Flum, Max Kubierschky, Bertram Ludäscher: Total and Partial Well-Founded Datalog Coincide. ICDT 1997: 113-124
5. Serge Abiteboul, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275
6. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
7. James J. Lu, Anil Nerode, V. S. Subrahmanian: Hybrid Knowledge Bases. IEEE Trans. Knowl. Data Eng. 8(5): 773-785(1996)
8. Jürgen Kalinski: Disjunctive Rules, Maybe Tuples and Null Values: Logic Programs with Incomplete Information. ADBIS 1996: 84-92
9. V. S. Subrahmanian, Dana S. Nau, Carlo Vago: WFS + Branch and Bound = Stable Models. IEEE Trans. Knowl. Data Eng. 7(3): 362-377(1995)
10. Teruhiro Shimura, Jorge Lobo, Tadao Murata: An Extended Petri Net Model for Normal Logic Programs. IEEE Trans. Knowl. Data Eng. 7(1): 150-162(1995)
11. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
12. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
13. V. S. Subrahmanian: Amalgamating Knowledge Bases. ACM Trans. Database Syst. 19(2): 291-331(1994)
14. Edward P. F. Chan: A Possible World Semantics for Disjunctive Databases. IEEE Trans. Knowl. Data Eng. 5(2): 282-292(1993)
15. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156
16. Shinichi Morishita: An Alternating Fixpoint Tailored to Magic Programs. PODS 1993: 123-134
17. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
18. Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104
19. Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32
20. Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163
21. Jia-Huai You, Li-Yan Yuan: Three-Valued Formalization of Logic Programming: Is It Needed? PODS 1990: 172-182
22. John S. Schlipf: The Expressive Powers of the Logic Programming Semantics. PODS 1990: 196-204
23. Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217
24. Nicole Bidoit, P. Legay: WELL!: An Evaluation Procedure for All Logic Programs. ICDT 1990: 335-348
25. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
26. Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21