Synthesis of Acyclic Models for Processes Without Repeating Events

Synthesis of Acyclic Models for Processes Without Repeating Events

Joulitov A.K. (NRU HSE, Moscow, Russia)
Lomazova I.A. (NRU HSE, Moscow, Russia)

Abstract

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.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 4, part 2, 2026, pp. 215-224

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(4)-27

For citation

Joulitov A.K., Lomazova I.A. Synthesis of Acyclic Models for Processes Without Repeating Events. Proceedings of the Institute for System Programming, vol. 38, issue 4, part 2, 2026, pp. 215-224 DOI: 10.15514/ISPRAS-2026-38(4)-27.

Full text of the paper in pdf Back to the contents of the volume