INCREMENTAL TRANSITION SYSTEM CONSTRUCTION WITH REFINEMENT FOR REGION-BASED PROCESS MINING

Authors

DOI:

https://doi.org/10.26034/lu.akwi.2026.8842

Keywords:

Region-based Process Mining, Incremental Algorithm, Transition System, Configuration Refinement

Abstract

Process discovery focuses on deriving process models from event logs to facilitate the analysis of complex workflows. Region-based approaches are known for their ability to effectively capture concurrency and handle invisible transitions, but they suffer from high computational demands and reliance on predefined state information. This paper introduces an incremental algorithm to construct transition systems (TS) from event logs, integrating a refinement strategy to optimize the representation of the state. The proposed method significantly reduces the complexity of the transition system by configuring state abstractions using past, future, or hybrid horizons. A refinement strategy is used to determine optimal configurations for state representation, ensuring model quality through precision and simplicity metrics. The approach is evaluated using a case study that demonstrates its effectiveness in improving scalability and efficiency in region-based process discovery.

Author Biographies

Shengrui Peng, L3S Research Center, Leibniz University Hannover

Shengrui Peng went to Leibniz University of Hanover, where he started with Civil Engineering as a Bachelor’s and obtained a Master’s degree in Computational Methods in Engineering in 2019. Immediately after graduation, he joined L3S Research Center as a Ph.D. candidate. He has published several papers on modeling, simulation-based optimization, and process mining. He is strongly interested in the concept of combining process mining techniques with advanced AI approaches.

Helena Szczerbicka, L3S Research Center, Leibniz University Hannover

Helena Szczerbicka is Professor Emeritus of the Faculty of Electrical Engineering and Computer Science at the Leibniz University of Hanover, Germany. Her research interests focus on modeling, simulation, and optimization. She has served on the Board of Directors of the Society of Modeling and Computer Simulation International SCS for many years. She has received much recognition for her various scholarly publications, achievements, and professional activities that focus on the importance of modeling and simulation in its interaction with other disciplines.

References

Adriano Augusto, Josep Carmona, and Eric Verbeek. Advanced Process Discovery Techniques. In Wil M. P. Van Der Aalst and Josep Carmona, editors, Process Mining Handbook, volume 448, pages 76–107. Springer International Publishing, Cham, 2022. doi: 10.1007/978-3-031-08848-3 3.

R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Process Mining Based on Regions of Languages. In G. Alonso, P. Dadam, and M. Rosemann, editors, Business Process Management, volume 4714, pages 375–383. Springer Berlin Heidelberg, 2007. doi: 10.1007/978-3-540-75183-0 27.

A. Berti, S. van Zelst, and D. Schuster. PM4Py: A process mining library for Python. Software Impacts, 17:1–7, September 2023. doi: 10.1016/j.simpa.2023.100556.

J.C.A.M. Buijs, B.F. van Dongen, and W.M.P. van der Aalst. On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery. In On the Move to Meaningful Internet Systems: OTM 2012, volume 7565, pages 305–322. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. doi: 10.1007/978-3-642-33606-5 19.

J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Synthesizing Petri nets from state-based models. In Proceedings of IEEE International Conference on Computer Aided Design (ICCAD), pages 164–171. IEEE, Nov. 5–9 1995. doi: 10.1109/ICCAD.1995.480008.

J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 47(8):859–882, August 1998. doi: 10.1109/12.707587.

J. Desel and W. Reisig. The synthesis problem of Petri nets. Acta Informatica, 33(4):297–315, 1996. doi: 10.1007/s002360050046.

A. Ehrenfeucht and G. Rozenberg. Partial (set) 2-structures: Part II: state spaces of concurrent systems. Acta Informatica, 27(4):343–368, March 1990. doi: 10.1007/BF00264612.

Humam Kourani, Alessandro Berti, Daniel Schuster, and Wil Van Der Aalst. Evaluating Large Language Models on Business Process Modeling: Framework, Benchmark, and Self-Improvement Analysis. 2024. doi: 10.13140/RG.2.2.11821.70880.

S. Peng and H Szczerbicka. Improvements to the region-based petri nets synthesis algorithm for process mining. In Proceedings of the 16th EAI International Conference on Simulation Tools and Techniques, Bratislava, 2024. EAI. C. A. Petri. Kommunikation mit Automaten. Phd thesis, Fakultat für Mathematik und Physik der Technischen Hochschule Darmstadt, 1962. Available at https://edoc.sub.uni-hamburg.de/informatik/volltexte/2011/160/.

S.A. Shershakov, A.A. Kalenkova, and I.A. Lomazova. Transition Systems Reduction: Balancing Between Precision and Simplicity. In M. Koutny, J. Kleijn, and W. Penczek, editors, Transactions on Petri Nets and Other Models of Concurrency XII, volume 10470, pages 119–139. Springer Berlin Heidelberg, Berlin, Heidelberg, 2017. doi: 10.1007/978-3-662-55862-1_6.

M. Sole and J. Carmona. Incremental process discovery. In ´Kurt Jensen, Susanna Donatelli, and Jetty Kleijn, editors, Transactions on Petri Nets and Other Models of Concurrency V, volume 6900, pages 221–242. Springer Berlin Heidelberg, 2012. doi: 10.1007/978-3-642-29072-510.

V. Teren, J. Cortadella, and T. Villa. Generation of synchronizing state machines from a transition system: A region-based approach. International Journal of Applied Mathematics and Computer Science, 33(1), 2023a. doi: 10.34768/amcs-2023-0011.

Viktor Teren, Jordi Cortadella, and Tiziano Villa. Seto: A Framework for the Decomposition of Petri Nets and Transition Systems. In 2023 26th Euromicro Conference on Digital System Design (DSD), pages 669–677, Golem, Albania, September 2023b. IEEE. doi: 10.1109/DSD60849.2023.00096.

W. M. P. van der Aalst. Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. doi: 10.1007/978-3-642-19345-3.

W. M. P. van der Aalst, V. Rubin, H. M. W. Verbeek, B. F. van Dongen, E. Kindler, and C. W. Gunther. Process mining: a two-step approach to balance between underfitting and overfitting. Software & Systems Modeling, 9(1):87–111, January 2010. doi: 10.1007/s10270-008-0106-z.

B. F. van Dongen and W. M. P. van der Aalst. Multi-phase Process Mining: Building Instance Graphs. In Conceptual Modeling – ER 2004, volume 3288, pages 362–376. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. doi: 10.1007/978-3-540-30464-7 29.

B.F. van Dongen and W.M.P. van der Aalst. Multi-phase process mining : Aggregating instance graphs into epcs and petri nets. In Proceedings of the Second International Workshop on Applications of Petri Nets to Coordination, Workflow and Business Process Management, 2005.

B.F. van Dongen, N. Busi, G.M. Pinna, and W.M.P van der Aalst. An iterative algorithm for applying the theory of regions in process mining. In Proceedings of the Workshop on Formal Approaches to Business Processes and Web Services, pages 36–55, Eindhoven, 2007. Publishing house of university of Podlasie.

Downloads

Published

2026-09-02

Issue

No. 22 (2026)

Section

Trends

License

Copyright (c) 2026 Shengrui Peng, Helena Szczerbicka

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.