Normal and sinkless petri nets
Resource
Journal of Computer and System Sciences 46 (1): 1-26
Journal
Journal of Computer and System Sciences
Journal Volume
46
Journal Issue
1
Pages
1-26
Date Issued
1993
Date
1993
Author(s)
Abstract
We examine both the modeling power of normal and sinkless Petri nets and the computational complexities of various classical decision problems with respect to these two classes. We argue that although neither normal nor sinkless Petri nets are strictly more powerful than persistent Petri nets, they nonetheless are both capable of modeling a more interesting class of problems. On the other hand, we give strong evidence that normal and sinkless Petri nets are easier to analyze than persistent Petri nets. In so doing, we apply techniques originally developed for conflict-free Petri nets-a class defined solely in terms of the structure of the net-to sinkless Petri nets-a class defined in terms of the behavior of the net. As a result, we give the first comprehensive complexity analysis of a class of potentially unbounded Petri nets defined in terms of their behavior. © 1993.
Other Subjects
Computational complexity; Parallel processing systems; Petri nets; Computational models; Computability and decidability
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
07.pdf
Size
1.65 MB
Format
Adobe PDF
Checksum
(MD5):fd34f7d0df4b09e10641c5543413ce04