Generation of Petri Nets Using Structural Property-Preserving Transformations
https://doi.org/10.15514/ISPRAS-2021-33(3)-12
Abstract
In this paper, we present an approach to the generation of Petri nets exhibiting desired structural and behavioral properties. Given a reference Petri net, we apply a collection of local refinement transformations, which extends the internal structure of the reference model. The correctness of applying these transformations is justified via Petri net morphisms and by the fact that transformations do not add new deadlocks to Petri nets. We have designed two Petri net refinement algorithms supporting the randomized and fixed generation of models. These algorithms have been implemented and evaluated within the environment of the Carassius Petri net editor. The proposed approach can be applied to evaluate and conduct experiments for algorithms operating with Petri nets.
Supporting agencies: This work is supported by the Basic Research Program at the National Research University Higher School of Economics (HSE University), Russia
About the Authors
Roman NESTEROV
HSE University, Univerist`a degli Studi di Milano-Bicocca
Russian Federation
Russian Federation
Postgraduate student at the Faculty of computer science, HSE University and at the Department of Informatics, System Engineering and Communications, University of Milano-Bicocca, Italy (UNIMIB), a junior research fellow at the Laboratory of Process-Aware Information Systems (PAIS Lab), HSE University
Semyon SAVELYEV
HSE University
Russian Federation
Russian Federation
Fourth-year undergraduate student at the Faculty of computer science, HSE University, a research assistant at the PAIS Lab, HSE University
References
1. W. Reisig. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer, 2013, 257 p.
2. J. Desel. Basic linear algebraic techniques for place/transition nets. Lecture Notes in Computer Science, vol. 1491. Springer, 1998, pp. 257-308.
3. N. Nikitina, A. Mitsyuk. Carassius: A Simple Process Model Editor. Trudy ISP RAN/Proc. ISP RAS, vol. 27, issue 3, 2015, pp.219-236. DOI: 10.15514/ISPRAS-2015-27(3)-15.
4. A. Burattin. Multiperspective process randomization with online and offline simulations. In Proc. of the BPM Demo Track 2016, CEUR Workshop Proceedings, vol. 1789, 2016, pp. 1-6.
5. A. Kalenkova, W. van der Aalst, I. Lomazova, and V. Rubin. Process mining using BPMN: relating event logs and process models. Software & Systems Modeling, vol. 16, 2017, pp. 1019-1048.
6. Z. Yan, R. Dijkman, and P. Grefen. Generating process model collections. Software & System Modeling, vol. 16, 2017, pp. 979-995.
7. T. Jouck and B. Depaire. PTandLogGenerator: A generator for artificial event data. In Proc. of the BPM Demo Track 2016, CEUR Workshop Proceedings, vol. 1789, 2016, pp. 23-27.
8. K. van Hee and Z. Liu. Generating benchmarks by random stepwise refinement of petri nets. In Proc. of the Workshops of the 31st International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (PETRI NETS 2010) and of the 10th International Conference on Application of Concurrency to System Design (ACSD 2010), CEUR Workshop Proceedings, vol. 827, 2010, pp. 403-417.
9. G. Berthelor. Checking properties of nets using transformations. Lecture Notes in Computer Science, vol. 222, 1986, pp. 19-40.
10. T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, vol. 77, no. 4, 1989, pp. 541-580.
11. T. Murata and I. Suzuki. A method for stepwise refinement and abstraction of Petri nets. Journal of Computer and System Sciences, vol. 27, issue 1, 1983, pp. 51-76.
12. G. Winskel. Petri nets, algebras, morphisms, and compositionality. Information and Computation, vol. 72, no. 3, 1987, pp. 197-238.
13. G. Winskel and M. Nielsen. Petri nets and bisimulations. Theoretical Computer Science, vol. 153, pp. 211-244, 1996.
14. J. Desel and A. Merceron. Vicinity respecting homomorphisms for abstracting system requirements. Lecture Notes in Computer, vol. 6550, 2010, pp. 1-20.
15. L. Bernardinello and F. De Cindio. A survey of basic net models and modular net classes. Lecture Notes in Computer Science, vol. 609, 1992, pp. 304-351.
16. L. Bernardinello, E. Mangioni, and L. Pomello. Local state refinement and composition of elementary net systems: An approach based on morphisms, Lecture Notes in Computer Science, vol. 8100, 2013, pp. 48-70.
17. L. Bernardinello, I. Lomazova, R. Nesterov, and L. Pomello. Property preserving transformations of elementary net systems based on morphisms. In Proc. of the International Workshop on Petri Nets and Software Engineering, CEUR Workshop Proceedings, vol. 2651, 2020, pp. 49-67.
18. N. Dingle, W. Knottenbelt, and T. Suto. PIPE2: A tool for the performance evaluation of generalised stochastic petri nets. ACM SIGMETRICS Performance Evaluation Review, vol. 36, no. 4, 2009, pp. 34-39.
19. Platform Independent Petri Net Editor. Available at https://github.com/sarahtattersall/PIPE, accessed: 2021-03-20.
20. PNEditor (Petri Net Editor). Available at https://github.com/matmas/pneditor, accessed: 2021-03-20.
21. T. Freytag and M. Sänger. WoPeD - An Educational Tool for Workflow Nets. in Proc. of the BPM Demo Sessions, ser. CEUR Workshop Proceedings, vol. 1295. CEUR-WS.org, 2014, pp. 31-36.
22. WoPeD (Workflow Petri Net Designer. Available at https://woped.dhbwkarlsruhe.de/, accessed: 2021-03-20.
23. WOLFGANG - Petri Net Editor. Available at https://github.com/iig-unifreiburg/WOLFGANG, accessed: 2021-03-20.
24. R. Nesterov and I. lomazova. Asynchronous interaction patterns for mining multi-agent system models from event logs. Proceedings of the MACSPro Workshop 2019, CEUR Workshop Proceedings, vol. 2478, 2019, pp. 62-73.
25. P.A. Pertsukhov, A.A. Mitsyuk. Simulating Petri Nets with Inhibitor and Reset Arcs. Trudy ISP RAN/Proc. ISP RAS, vol. 31, issue 4, 2019. pp. 151-162. DOI: 10.15514/ISPRAS-2019-31(4)-1.
26. A. Barros, M. Dumas, and A. ter Hofstede. Service interaction patterns. Lecture Notes in Computer Science, vol. 3649, 2005, pp. 302-318.
Review
For citations:
NESTEROV R., SAVELYEV S. Generation of Petri Nets Using Structural Property-Preserving Transformations. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2021;33(3):155-170. https://doi.org/10.15514/ISPRAS-2021-33(3)-12
Email this article 