An Extended Petri Net Model for Normal Logic Programs.

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)

@article{DBLP:journals/tkde/ShimuraLM95,
  author    = {Teruhiro Shimura and
               Jorge Lobo and
               Tadao Murata},
  title     = {An Extended Petri Net Model for Normal Logic Programs},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {7},
  number    = {1},
  year      = {1995},
  pages     = {150-162},
  ee        = {db/journals/tkde/ShimuraLM95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper presents an application of the concepts of siphons (deadlocks) and inhibitor arcs in Petri net theory to logic programs with negations. More specifically, an extended Petri net is used to model function-free normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary applications of firing rule may cause a contradictory situation. We suggest two directions to avoid contradictions: greedy and secure applications of firing rule. We choose the secure application in this paper and show that this is a direct translation of the well-founded semantics in the net model. Furthermore, we show that the greatest unfounded set corresponds to the greatest siphon in Petri net theory when we delete the transitions disabled by the secure application of firing rule, and that the property of siphon simplifies the computation of well-founded semantics for logic programs. We also propose the reduced-Petri-net method by which we can reduce an extended Petri net to a Petri net without inhibitor arcs and compute the well-founded model by iterative applications of this transformation using conventional application of firing rule.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-3 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[1]: Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982)
[2]: Chitta Baral, V. S. Subrahmanian: Dualities between Alternative Semantics for Logic Programming and Nonmonotonic Reasoning (Extended Abstract). LPNMR 1991: 69-86
[3]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080
[4]: Michael Gelfond, Halina Przymusinska: Definitions in Epistemic Specifications. LPNMR 1991: 245-259
[5]: Vladimir Lifschitz: Logical Foundations of Deductive Databases. IFIP Congress 1989: 315-321
[6]: ...
[7]: John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
[8]: V. Wiktor Marek, V. S. Subrahmanian: The Relationship Between Logic Program Semantics and Non-Monotonic Reasoning. ICLP 1989: 600-617
[9]: ...
[10]: Tadao Murata, V. S. Subrahmanian, Toshiro Wakayama: A Petri Net Model for Reasoning in the Presence of Inconsistency. IEEE Trans. Knowl. Data Eng. 3(3): 281-292(1991)
[11]: ...
[12]: Tadao Murata, Du Zhang: A Predicate-Transition Net Model for Parallel Interpretation of Logic Programs. IEEE Trans. Software Eng. 14(4): 481-497(1988)
[13]: ...
[14]: Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21
[15]: Teodor C. Przymusinski: On the Declarative Semantics of Deductive Databases and Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 193-216
[16]: Teodor C. Przymusinski: Three-Valued Formalizations of Non-Monotonic Reasoning and Logic Programming. KR 1989: 341-348
[17]: Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980)
[18]: ...
[19]: Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976)
[20]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10
[21]: Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991)
[22]: ...
[23]: ...