Генерация сетей Петри с помощью структурных трансформаций, сохраняющих поведенческие свойства
https://doi.org/10.15514/ISPRAS-2021-33(3)-12
Аннотация
В работе предложен подход к генерации сетей Петри, обладающих желаемыми структурными и поведенческими свойствами. На вход подается эталонная сеть Петри, к которой применяется набор локальных трансформаций, расширяющих ее внутреннюю структуру. Корректность применения этих трансформаций обуславливается тем, что они порождают морфизмы на сетях Петри, а также не добавляют новых тупиков при расширении эталонных сетей Петри. Таким образом, сохраняются поведенческие и структурные свойства, которыми обладает эталонная сеть Петри. Были разработаны алгоритмы фиксированной и случайной генерации сетей Петри. Эти алгоритмы реализованы в виде расширения для редактора сетей Петри Carassius. Кроме того, проведена экспериментальная оценка разработанных алгоритмов. Предлагаемый подход к генерации сетей Петри и разработанные алгоритмы могут применяться для проведения комплексной экспериментальной оценки и нагрузочного тестирования алгоритмов, на вход которым подаются модели поведения процессов в виде сетей Петри.
При поддержке: Работа поддержана Программой фундаментальных исследований Национального исследовательского университета «Высшая школа экономики» (НИУ ВШЭ), Россия.
Об авторах
Роман Александрович НЕСТЕРОВ
Национальный исследовательский университет Высшая школа экономики, Миланский университет-Бикокка
Россия
Россия
Аспирант факультета компьютерных наук НИУ ВШЭ и департамента информатики, системной инженерии и коммуникаций Миланского университета Бикокка (UNIMIB), младший научный сотрудник лаборатории ПОИС НИУ ВШЭ
Семен Юрьевич САВЕЛЬЕВ
Национальный исследовательский университет Высшая школа экономики
Россия
Россия
Cтудент четвертого курса бакалавриата факультета компьютерных наук НИУ ВШЭ, стажер-исследователь лаборатории ПОИС НИУ ВШЭ
Список литературы
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.
Рецензия
Для цитирования:
НЕСТЕРОВ Р.А., САВЕЛЬЕВ С.Ю. Генерация сетей Петри с помощью структурных трансформаций, сохраняющих поведенческие свойства. Труды Института системного программирования РАН. 2021;33(3):155-170. https://doi.org/10.15514/ISPRAS-2021-33(3)-12
For citation:
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
Послать статью по эл. почте 