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.
