Normal and sinkless Petri nets (Q1208921)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Normal and sinkless Petri nets |
scientific article |
Statements
Normal and sinkless Petri nets (English)
0 references
16 May 1993
0 references
The modelling power of conflict-free, persistent [\textit{L. Landweber} and \textit{R. Robertson}, Properties of conflict-free and persistent Petri nets, J. Assoc. Comput. Machin. 25, 352-364 (1978; Zbl 0384.68062)], normal and sinkless [\textit{H. Yamasaki}, Normal Petri nets, Theor. Comput. Sci. 31, 307-315 (1984; Zbl 0562.68047)], Petri nets and the computational complexities of various classical decision problems with respect to these classes are discussed. The following relations are shown: \[ \begin{matrix} &\Sigma_ N\subset \Sigma_ S\\ \Sigma_{CF}\subset &&\subset\Sigma_{PN},\\ &\Sigma_ P\end{matrix} \] where \(\Sigma_{CF}\), \(\Sigma_ N\), \(\Sigma_ P\), \(\Sigma_ S\) and \(\Sigma_{PN}\) are the classes of Conflict-Free, Normal, Persistent, Sinkless and (ordinary) Petri nets. The reviewer would like to formulate two questions related to the text and whose answers will extend the interesting results of the three authors: 1. Is there a net which is an element of \(\Sigma_{PN}-(\Sigma_ P\cup\Sigma_ S)\) and what is its type? 2. What are the relations with respect to the above types of nets and the regular Petri nets [\textit{V. Kotov}, An algebra for parallelism based on Petri nets, Lect. Notes Comput. Sci. 64, 39-55 (1978; Zbl 0383.68029)]?
0 references
conflict-free nets
0 references
normal nets
0 references
persistent nets
0 references
sinkless nets
0 references
Petri nets
0 references
0 references
0 references