Evaluating Structural Complexity of Workflow Nets Modeling Asynchronous Agent Interactions
https://doi.org/10.15514/ISPRAS-2025-37(4)-18
Abstract
The structure of a process model discovered from an event log of a multi-agent system often does not reflect the system architecture with respect to agent interactions. The existing conformance checking quality dimensions mainly evaluate the extent to which the behavior a discovered model corresponds to event sequences recorded in an event log. These behavioral dimensions might be insufficient to differentiate process models discovered from an event log of the same multi-agent system with respect to the independence of agents and the complexity of their interactions. In this work, we propose a theoretically grounded approach to measuring the structural complexity of a process model representing a multi-agent system with asynchronously interacting agents. We also report the key outcomes from a series of experiments to evaluate the sensitivity of the proposed approach to structural modifications in process models.
Keywords
multi-agent systems,
asynchronous interaction,
process mining,
Petri nets,
workflow nets,
structural complexity.
Supporting agencies: This work was supported by the Basic Research Program at the HSE University, Moscow (Russia)
About the Authors
Roman Alexandrovich NESTEROV
HSE University
Russian Federation
Russian Federation
Cand. Sci. (Computer Science), Associate Professor at the Department of Software Engineering at the Faculty of Computer Science, Head of the Laboratory of Process-Aware Information Systems (PAIS Lab), HSE University (Moscow, Russia). His research interests include approaches to modeling and analyzing the behavior of complex information systems using Petri nets, category theory, and the general theory of parallelism.
Egor Olegovich ZEMLYANOY
HSE University
Russian Federation
Russian Federation
А research assistant at the Laboratory of Process-Aware Information Systems (PAIS Lab), HSE University (Moscow, Russia), MSc in Software engineering since 2025. Research interests: modeling and analysis of distributed information systems behaviors using Petri nets and their extensions.
References
1. W. van der Aalst, Process Mining: Data Science in Action. Springer Heidelberg, 2016. URL: https://link.springer.com/book/10.1007/978-3-662-49851-4.
2. A. Augusto, R. Conforti, M. Dumas, M. L. Rosa, F. M. Maggi, A. Marrella, M. Mecella, and A. Soo, Automated discovery of process models from event logs: Review and benchmark, IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 4, pp. 686–705, 2019. URL: https://ieeexplore.ieee.org/document/8368306.
3. W. Reisig, Understanding Petri nets. Modeling techniques, analysis methods, case studies. Springer Heidelberg, 2013. URL: https://link.springer.com/book/10.1007/978-3-642-33278-4.
4. A. Kalenkova, A. Burattin, and M. a. de Leoni, Discovering high-level BPMN process models from event data, Business Process Management Journal, vol. 25, pp. 995–1019, 2019. URL: https://www.emerald.com/bpmj/article/25/5/995/256745/Discovering-high-level-BPMN-process-models-from.
5. J. Carmona, B. van Dongen, A. Solti, and M. Weidlich, Conformance Checking: Relating Processes and Models. Springer Heidelberg, 2018. URL: https://link.springer.com/book/10.1007/978-3-319-99414-7.
6. A. Adriansyah, J. Munoz-Gama, J. Carmona, B. van Dongen, and W. van der Aalst, Alignment based precision checking, in Business Process Management Workshops, ser. LNBIP, vol. 132. Springer Heidelberg, 2013, pp. 137–149. URL: https://link.springer.com/chapter/10.1007/978-3-642-36285-9_15.
7. S. Leemans, D. Fahland, and W. van der Aalst, Discovering block- structured process models from event logs – a constructive approach, in PETRI NETS, ser. LNCS, J. Colom and J. Desel, Eds., vol. 7927. Springer Heidelberg, 2013, pp. 311–329.
8. URL: https://link.springer.com/chapter/10.1007/978-3-642-38697-8_17.
9. W. M. van der Aalst, Relating process models and event logs – 21 conformance propositions, in ATAED@Petri Nets/ACSD, 2018. [Online]. URL: https://api.semanticscholar.org/CorpusID:49303433
10. W. van der Aalst, Workflow verification: Finding control-flow errors using petri-net-based techniques, in Business Process Management: Models, Techniques, and Empirical Studies, ser. LNCS, vol. 1806. Springer, Heidelberg, 2000, pp. 161–183.
11. URL: https://link.springer.com/chapter/10.1007/3-540-45594-9_11.
12. L. Bernardinello, I. Lomazova, R. Nesterov, and P. L., Soundness-preserving composition of synchronously and asynchronously interacting workflow net components, Journal of Parallel and Distributed Computing, vol. 179, Article 104704, 2023. URL: https://www.sciencedirect.com/science/article/pii/S0743731523000679.
13. R. Nesterov, L. Bernardinello, I. Lomazova, and P. L., Discovering architecture-aware and sound process models of multi-agent systems: a compositional approach, Software and Systems Modeling, vol. 22, pp. 351–375, 2023. URL: https://link.springer.com/article/10.1007/s10270-022-01008-x.
14. L. Bernardinello, E. Mangioni, and L. Pomello, Local state refinement and composition of elementary net systems: An approach based on morphisms, in Transactions on Petri Nets and Other Models of Concurrency VIII, ser. LNCS, vol. 8100. Springer, Heidelberg, 2013, pp. 48–70. URL: https://link.springer.com/chapter/10.1007/978-3-642-40465-8_3.
15. E. Zemlyanoy, Structural complexity of workflow nets [Online]. URL: https://github.com/egorz734/ structural-complexity-of-workflow-nets.
16. C. Gunther and W. van der Aalst, Fuzzy mining – adaptive process simplification based on multi-perspective metrics, in Business Process Management, ser. LNCS, G. Alonso, P. Dadam, and M. Rosemann, Eds., vol. 4714. Springer Heidelberg, 2007, pp. 328–343. URL: https://link.springer.com/chapter/10.1007/978-3-540-75183-0_24.
17. J. van der Werf, B. van Dongen, C. Hurkens, and A. Serebrenik, Process discovery using integer linear programming, in PETRI NETS, ser. LNCS, K. van Hee and R. Valk, Eds., vol. 5062. Springer Heidelberg, 2008, pp. 368–387. URL: https://link.springer.com/chapter/10.1007/978-3-540-68746-7_24.
18. T. McCabe, A complexity measure, IEEE Transactions on Software Engineering, vol. SE-2, no. 4, pp. 308-320, 1976. URL: https://ieeexplore.ieee.org/document/1702388.
19. L. Gang Soo and Y. Jung-Mo, An empirical study on complexity metrics of petri nets, Microelectronics Reliability, vol. 32, no. 9, pp. 1215–1221, 1992. URL: https://www.sciencedirect.com/science/article/pii/002627149290061O.
20. A. Kalenkova, A. Lomazova, and W. van der Aalst, Process model discovery: A method based on transition system decomposition, in PETRI NETS, ser. LNCS, G. Ciardo and E. Kindler, Eds., vol. 8489. Springer Heidelberg, 2014, pp. 71–90.
21. URL: https://link.springer.com/chapter/10.1007/978-3-319-07734-5_5.
22. A. Kalenkova and I. Lomazova, Discovery of cancellation regions within process mining techniques, Fundamenta Informaticae, vol. 133, pp. 197–209, 2014. URL: https://journals.sagepub.com/doi/abs/10.3233/FI-2014-1071.
23. W. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek, Process discovery using localized events, in PETRI NETS, ser. LNCS, R. Devillers and A. Valmari, Eds., vol. 9115. Springer Heidelberg, 2015, pp. 287–308. URL: https://link.springer.com/chapter/10.1007/978-3-319-19488-2_15.
24. A. Begicheva, I. Lomazova, and R. Nesterov, Discovering hierarchical process models: an approach based on events partitioning, Modeling and Analysis of Information Systems, vol. 31, no. 3, pp. 294–315, 2024. URL: https://www.mais-journal.ru/jour/article/view/1879.
25. A. Begicheva and I. Lomazova, Discovering high-level process models from event logs, Modeling and Analysis of Information Systems, vol. 24, no. 2, pp. 125–140, 2017. URL: https://www.mais-journal.ru/jour/article/view/504.
26. W. van der Aalst and A. Berti, Discovering object-centric petri nets, Fundamenta Informaticae, vol. 175, pp. 1–40, 2020. URL: https://journals.sagepub.com/doi/10.3233/FI-2020-1946.
Supplementary files
Review
For citations:
NESTEROV R.A., ZEMLYANOY E.O. Evaluating Structural Complexity of Workflow Nets Modeling Asynchronous Agent Interactions. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(4):47-68. https://doi.org/10.15514/ISPRAS-2025-37(4)-18
Email this article 