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)
  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,}


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.

Copyright © 1995 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
Chitta Baral, V. S. Subrahmanian: Dualities between Alternative Semantics for Logic Programming and Nonmonotonic Reasoning (Extended Abstract). LPNMR 1991: 69-86 BibTeX
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
Michael Gelfond, Halina Przymusinska: Definitions in Epistemic Specifications. LPNMR 1991: 245-259 BibTeX
Vladimir Lifschitz: Logical Foundations of Deductive Databases. IFIP Congress 1989: 315-321 BibTeX
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
V. Wiktor Marek, V. S. Subrahmanian: The Relationship Between Logic Program Semantics and Non-Monotonic Reasoning. ICLP 1989: 600-617 BibTeX
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) BibTeX
Tadao Murata, Du Zhang: A Predicate-Transition Net Model for Parallel Interpretation of Logic Programs. IEEE Trans. Software Eng. 14(4): 481-497(1988) BibTeX
Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX
Teodor C. Przymusinski: On the Declarative Semantics of Deductive Databases and Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 193-216 BibTeX
Teodor C. Przymusinski: Three-Valued Formalizations of Non-Monotonic Reasoning and Logic Programming. KR 1989: 341-348 BibTeX
Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
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. Jacques Calmet, Dirk Debertin, Sebastian Jekutsch, Joachim Schü: An Executable Graphical Representation of Mediatory Information Systems. ICDE 1996: 124-131
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM ( and IEEE, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:28:15 2009