scientific article; zbMATH DE number 17543
[For the entire collection see Zbl 0726.00019.] The modelling power of normal and sinkless Petri nets is examined and compared with that of conflict-free and persistent ones. In particular, it is shown that neither a more general producer/consumer problem nor the mutual exclusion problem can be modeled by persistent Petri nets. But although the mutual exclusion problem cannot be modeled even by sinkless Petri nets, the generalized producer/consumer problem and a version of the mutual exclusion problem in which the total number of exclusions in many computation is bounded by a fixed constant both can be modeled by normal Petri nets and hence by sinkless ones. Moreover persistent ones cannot model one exclusion. Later the complexity problems are examined. It is argued that normal and sinkless Petri nets are easier to analyze than persistent Petri nets. Doing so 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 behavior of the net are applied. As a result the first comprehensive complexity analysis of a class of potentially unbounded Petri nets defined in terms of their behaviour is given.
- The complexity of problems involving structurally bounded and conservative Petri nets
- A unified approach for deciding the existence of certain petri net paths
- Normal and sinkless Petri nets
- Fair Petri nets and structural induction for rings of processes
- scientific article; zbMATH DE number 4096792 (Why is no real title available?)
- A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application
- scientific article; zbMATH DE number 5263412 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974867)