Evaluating Structural Complexity of Workflow Nets Modeling Asynchronous Agent Interactions

Proceedings of the Institute for System Programming of the RAS. 2025. Vol. 37. No. 4-2. P. 47–68.

Е. Zemlyanoy, R. Nesterov

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: структурная сложность, сети Петри, structural complexity, Petri nets, multi-agent systems, многоагентные системы, workflow nets, Асинхронное взаимодействие, синтез моделей процессов, сети потоков работ, asynchronous interaction, process mining

Publication based on the results of: New methods in the study of formal computation models, computer systems and related theoretical computer science problems (2025)