ACM SIGMOD Anthology TKDE dblp.uni-trier.de

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}
}
BibTeX

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.

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

References

[1]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
[2]
Chitta Baral, V. S. Subrahmanian: Dualities between Alternative Semantics for Logic Programming and Nonmonotonic Reasoning (Extended Abstract). LPNMR 1991: 69-86 BibTeX
[3]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[4]
Michael Gelfond, Halina Przymusinska: Definitions in Epistemic Specifications. LPNMR 1991: 245-259 BibTeX
[5]
Vladimir Lifschitz: Logical Foundations of Deductive Databases. IFIP Congress 1989: 315-321 BibTeX
[6]
...
[7]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[8]
V. Wiktor Marek, V. S. Subrahmanian: The Relationship Between Logic Program Semantics and Non-Monotonic Reasoning. ICLP 1989: 600-617 BibTeX
[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) BibTeX
[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) BibTeX
[13]
...
[14]
Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX
[15]
Teodor C. Przymusinski: On the Declarative Semantics of Deductive Databases and Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 193-216 BibTeX
[16]
Teodor C. Przymusinski: Three-Valued Formalizations of Non-Monotonic Reasoning and Logic Programming. KR 1989: 341-348 BibTeX
[17]
Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX
[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) BibTeX
[20]
Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
[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) BibTeX
[22]
...
[23]
...

Referenced by

  1. Jacques Calmet, Dirk Debertin, Sebastian Jekutsch, Joachim Schü: An Executable Graphical Representation of Mediatory Information Systems. ICDE 1996: 124-131
BibTeX
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 (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:28:15 2009