Abstract
A set of necessary conditions for a Petri net to be plain, pure and safe is given. Some applications of these conditions both in practice (for Petri net synthesis), and in theory (e.g., as part of a characterisation of the reachability graphs of live and safe marked graphs) are described.
K. Barylska—Co-funded by project PO KL Information technologies: Research and their interdisciplinary applications, Agreement UDA-POKL.04.01.01-00-051/10-00 and by the Polish National Science Center (grant No.2013/09/D/ST6/03928).
U. Schlachter—Supported by DFG (German Research Foundation) through grant Be 1267/15-1 ARS (Algorithms for Reengineering and Synthesis).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Unless infinite nets are considered, which we shall exclude in this paper.
- 2.
Characterisations have been obtained for more restricted classes, e.g. in [4].
- 3.
S can also be considered as a set of vertices and \(\rightarrow \) as a set of edges of a directed graph, labelled by letters from T.
- 4.
In this paper, no arc weights greater than 1 will be considered.
- 5.
This can be verified easily by playing the “token game” in the latter.
- 6.
Note that p is the only unsafe place (with bound 2), and that \(L'\) is the only non-safe reachable marking. In this sense, the example demonstrates that the conjecture is sharp. We also believe that it is the smallest example with this property.
- 7.
- 8.
Note that there is also a short path \(s_a[a\rangle 1[c\rangle 2[d\rangle 4[a\rangle 5[c\rangle s_b\) containing a two times. However, this path is not indicative of an unsafe place from a to b, since \(s_a\notin Seq(b)\).
References
Badouel, É., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary nets is NP-complete. Theor. Comput. Sci. 186, 107–134 (1997)
Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series, p. 339. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47967-4
Best, E., Devillers, R.: Sequential and concurrent behaviour in Petri net theory. Theor. Comput. Sci. 55(1), 87–136 (1987)
Best, E., Devillers, R.: Characterisation of the state spaces of marked graph Petri nets. In: Selected papers of LATA 2014, Information and Computation, vol. 253, Part 3, pp. 399–410 (2014). http://dx.doi.org/10.1016/j.ic.2016.06.006
Best, E., Schlachter, U.: Analysis of Petri nets and transition systems. In: Proceedings of 8th Interaction and Concurrency Experience, In: Knight, S., Lanese, I., Lafuente, A.L., Vieira, H.T. (eds.) 189 of Electronic Proceedings in Theoretical Computer Science, pp. 53–67, June 2015. http://eptcs.web.cse.unsw.edu.au/paper.cgi?ICE2015.6, https://github.com/CvO-Theory/apt
Commoner, F., Holt, A.W., Even, S., Pnueli, A.: Marked directed graphs. J. Comput. Syst. Sci. 5(5), 511–523 (1971)
Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving petri nets for finite transition systems. IEEE Trans. Comput. 47(8), 859–882 (1998)
Esparza, J.: Decidability and complexity of Petri net problems — an introduction. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 374–428. Springer, Heidelberg (1998). doi:10.1007/3-540-65306-6_20
Landweber, L.H., Robertson, E.L.: Properties of conflict-free and persistent Petri nets. JACM 25(3), 352–364 (1978)
Lehmann, D., Pnueli, A., Stavi, J.: Impartiality, justice and fairness: the ethics of concurrent termination. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 264–277. Springer, Heidelberg (1981). doi:10.1007/3-540-10843-2_22
Ochmański, E.: On conflict-free executions of elementary nets. Systems Science, 27, Nr. 2, Wydawca Oficyna Wydawnicza Politechniki Wrocławskiej, 89–105. Also: Persistent Runs in Elementary Nets. FolCo Technical report, Nicol. Copernic. Univ. of Toruń, 2014 (2001)
Ochmański, E.: Occurrence traces: processes of elementary net systems. In: Rozenberg, G. (ed.) APN 1987. LNCS, vol. 340, pp. 331–342. Springer, Heidelberg (1988). doi:10.1007/3-540-50580-6_36
Pomello, L., Simone, C.: An algebraic characterisation of elementary net system (observable) state space. Formal Aspects Comput. 4(6A), 612–637 (1992)
Reisig, W.: Petri Nets: An Introduction. Monographs in Theoretical Computer Science. An EATCS Series, vol. 4. Springer, Heidelberg (1985). doi:10.1007/978-3-642-69968-9
Rozenberg, G.: Behaviour of elementary net systems. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) ACPN 1986. LNCS, vol. 254, pp. 60–94. Springer, Heidelberg (1987). doi:10.1007/978-3-540-47919-2_4
Thiagarajan, P.S.: Elementary net systems. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) ACPN 1986. LNCS, vol. 254, pp. 26–59. Springer, Heidelberg (1987). doi:10.1007/978-3-540-47919-2_3
Schlachter, U.: Petri net synthesis for restricted classes of nets. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 79–97. Springer, Cham (2016). doi:10.1007/978-3-319-39086-4_6
Acknowledgment
The authors are grateful to the reviewers for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer-Verlag GmbH Germany
About this chapter
Cite this chapter
Barylska, K., Best, E., Schlachter, U., Spreckels, V. (2017). Properties of Plain, Pure, and Safe Petri Nets. In: Koutny, M., Kleijn, J., Penczek, W. (eds) Transactions on Petri Nets and Other Models of Concurrency XII. Lecture Notes in Computer Science(), vol 10470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-55862-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-55862-1_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-55861-4
Online ISBN: 978-3-662-55862-1
eBook Packages: Computer ScienceComputer Science (R0)