Equivalences and Properties of Petri Nets vs. Block-structured Business Process Modeling Languages

One of the most recently regarded research area in the Business Process Management (BPM) field is the construction of Digital Process Twins (DPTs) [Bee+23], "a comprehensive digital replica of the system behavior." [Cor+22]. A plethora of business process modeling languages, e.g. the Business Process Modeling Notation (BPMN), the Unified Modeling Language Activity Diagram (UML AD) or Yet Another Workflow Language (YAWL) have been proposed and are widely used. Most of these business process modeling languages were inspired by Petri nets and add good ideas, but many are also considered semi-formal and are therefore hard to analyze [Aal02]. Petri nets describe a good starting point for business process models as they provide a graphical representation, have clear semantics and a wide range of analysis techniques exist [Aal02]. Petri nets are therefore widely used for academic purposes in research and for educational purposes.

However, Petri nets also allow for structural complexity that hinder efficient analysis, e.g., deciding behavioral soundness, processing, e.g., parsing of Petri nets, changes, e.g., changing the structure of Petri nets, and understandability, e.g., visualizing Petri nets [Van+09,San+13]. Therefore, block-structured business process modeling languages such as the Refined Process Structure Tree (RPST) [Van+09] and Process Trees [San+13] have been proposed to overcome the limitations inherent to the more general Petri nets. Transformations from Petri nets to RPSTs and Process Trees exist [Van+09,Zelst+20], but a complete overview and analysis on what equivalences hold between original Petri nets and their transformed counterparts is lacking. Additionally, a comprehensive analysis of Petri net properties resulting in the aformentioned limitations and a comparison to corresponding properties in block-structured languages is missing. Lastly, it is not clear what tool support for transformations exist.

Therefore, the BPM research community, as well as BPM courses, could benefit from a comprehensive overview, analysis and comparison of Petri nets vs. block-structured languages.

The purpose of this Master thesis is first to identify relevant work on Petri net properties and analysis problems relative to block-structured languages for a comprehensive overview, and, then deriving properties that are responsible for differences and equivalences between Petri nets and block-structured languages to clarify formal relationships between these languages. Additionally, uncovering limitations of existing tool support for transformations and implementing an extension to an existing tool to overcome a selected limitation would be favourable.

Prerequisites: (1) Knowledge of graph theory (2) Theoretical foundations in formal languages and logic. (3) Knowledge of programming languages and software engineering.

Contact: master.i17 [at] in.tum.de

[Aal02] Wil M. P. van der Aalst. “Making Work Flow: On the Application of Petri Nets to Business Process Management”. In: Application and Theory of Petri Nets 2002. Ed. by Javier Esparza and Charles Lakos. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2002, pp. 1–22. isbn: 978-3-540-48068-6. doi: 10.1007/3-540-48068-4_1.
[Bee+23] Iris Beerepoot et al. “The biggest business process management problems to solve before we die”. In: Computers in Industry 146 (Apr. 2023), p. 103837.  issn: 0166-3615. doi: 10 . 1016 / j .  compind . 2022 . 103837. url: https : / / www . sciencedirect . com / science / article / pii / S0166361522002330 (visited on 01/05/2023).
[Cor+22] Flavio Corradini et al. “An Approach to Support Digital Process Twin”. In: 2022 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech).  Sept. 2022, pp. 1–4. doi: 10 . 1109 / 1DASC/PiCom/CBDCom/Cy55231.2022.  9927841

[Van+09]

Jussi Vanhatalo et al. 2009. “The Refined Process Structure Tree.” Data & Knowledge Engineering, Sixth International Conference on Business Process Management (BPM 2008) – Five selected and extended papers, 68 (9): 793–818. doi.org/10.1016/j.datak.2009.02.015.

[San+13] Sander J. J. Leemans et al. 2013. “Discovering Block-Structured Process Models from Event Logs - A Constructive Approach.” In Application and Theory of Petri Nets and Concurrency, edited by José-Manuel Colom and Jörg Desel, 311–29. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-38697-8_17.

[Zelst+20] Zelst, Sebastiaan J. van, and Sander J. J. Leemans. 2020. “Translating Workflow Nets to Process Trees: An Algorithmic Approach.” Algorithms 13 (11): 279. https://doi.org/10.3390/a13110279.