Synthesis of Acyclic Models for Processes Without Repeating Events

Proceedings of the Institute for System Programming of the RAS. 2026. Vol. 38. No. 4(2) . P. 215–224.

Joulitov A.K., Lomazova I.A.

In process mining, DFG (Directly-Follows Graph) models are popular due to their simplicity and clarity. However, if a process is acyclic but contains concurrent events, standard algorithms for discovering DFG models can generate "fake" cycles that do not actually exist in the event log. These cycles hinder the analysis of information processes, significantly reducing the quality and precision of the model. This problem was studied by N. Shaimov et al., where it was proposed to discover DFG models without false cycles by duplicating graph vertices. This problem does not have a single or best solution, and the solution proposed there is heuristic. The aim of this paper is to propose an alternative algorithm for discovering acyclic DFG models for processes without repeating events and to compare it with the existing one on real-life and artificial data. The method presented in this paper produces a smaller model than existing solution and is stable when constructing models of highly concurrent processes. It is also proved that eliminating false cycles for highly concurrent processes leads to an exponential increase in the model size.

Keywords: майнинг процессов, графы непосредственного следования, process mining, automatic model synthesis, directly follows graphs, acyclic models, автоматический синтез моделей, ациклические модели

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