{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T19:48:58Z","timestamp":1784404138510,"version":"3.55.0"},"reference-count":34,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Since their introduction, process trees have been frequently used as a process modeling formalism in many process mining algorithms. A process tree is a (mathematical) tree-based model of a process, in which internal vertices represent behavioral control-flow relations and leaves represent process activities. Translation of a process tree into a sound workflow net is trivial. However, the reverse is not the case. Simultaneously, an algorithm that translates a WF-net into a process tree is of great interest, e.g., the explicit knowledge of the control-flow hierarchy in a WF-net allows one to reason on its behavior more easily. Hence, in this paper, we present such an algorithm, i.e., it detects whether a WF-net corresponds to a process tree, and, if so, constructs it. We prove that, if the algorithm finds a process tree, the language of the process tree is equal to the language of the original WF-net. The experiments conducted show that the algorithm\u2019s corresponding implementation has a quadratic time complexity in the size of the WF-net. Furthermore, the experiments show strong evidence of process tree rediscoverability.<\/jats:p>","DOI":"10.3390\/a13110279","type":"journal-article","created":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T19:51:31Z","timestamp":1604346691000},"page":"279","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Translating Workflow Nets to Process Trees: An Algorithmic Approach"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0415-1036","authenticated-orcid":false,"given":"Sebastiaan J.","family":"van Zelst","sequence":"first","affiliation":[{"name":"Institute for Applied Information Technology (FIT), Fraunhofer Gesellschaft, 53754 Sankt Augustin, Germany"},{"name":"Chair of Process and Data Science, RWTH Aachen University, 52074 Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5201-7125","authenticated-orcid":false,"given":"Sander J. J.","family":"Leemans","sequence":"additional","affiliation":[{"name":"School of Information Systems, Queensland University of Technology, Brisbane City QLD 4000, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"van der Aalst, W.M.P. (2016). Process Mining\u2014Data Science in Action, Springer. [2nd ed.].","DOI":"10.1007\/978-3-662-49851-4"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1016\/j.infsof.2008.02.006","article-title":"Semantics and analysis of business process models in BPMN","volume":"50","author":"Dijkman","year":"2008","journal-title":"Inf. Softw. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/S0950-5849(99)00016-6","article-title":"Formalization and verification of event-driven process chains","volume":"41","year":"1999","journal-title":"Inf. Softw. Technol."},{"key":"ref_4","unstructured":"van der Aalst, W.M.P., Buijs, J.C.A.M., and van Dongen, B.F. (July, January 29). Towards Improving the Representational Bias of Process Mining. Proceedings of the SIMPDA, Campione d\u2019Italia, Italy."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.ins.2018.07.026","article-title":"Recomposing conformance: Closing the circle on decomposed alignment-based conformance checking in process mining","volume":"466","author":"Lee","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_6","first-page":"1","article-title":"Computing Alignments of Event Data and Process Models","volume":"13","author":"Bolt","year":"2018","journal-title":"ToPNoC"},{"key":"ref_7","unstructured":"Schuster, D., van Zelst, S.J., and van der Aalst, W.M.P. (2020, January 18). Alignment Approximation for Process Trees (forthcoming). Proceedings of the 5th International Workshop on Process Querying, Manipulation, and Intelligence (PQMI 2020), Padua, Italy."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"van der Aalst, W.M.P., de Medeiros, A.K.A., and Weijters, A.J.M.M. (2006, January 5\u20137). Process Equivalence: Comparing Two Process Models Based on Observed Behavior. Proceedings of the Business Process Management, 4th International Conference, BPM 2006, Vienna, Austria.","DOI":"10.1007\/11841760_10"},{"key":"ref_9","unstructured":"Krogstie, J., Pastor, O., Pernici, B., Rolland, C., and S\u00f8lvberg, A. (2013). Measuring Similarity between Business Process Models. Seminal Contributions to Information Systems Engineering, 25 Years of CAiSE, Springer."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1504\/IJBPIM.2008.020973","article-title":"On the transformation of control flow between block-oriented and graph-oriented process modelling languages","volume":"3","author":"Mendling","year":"2008","journal-title":"IJBPIM"},{"key":"ref_11","unstructured":"Berti, A., van Zelst, S.J., and van der Aalst, W.M.P. (2019, January 24\u201326). Process Mining for Python (PM4Py): Bridging the Gap Between Process-and Data Science. Proceedings of the ICPM Demo Track 2019, Aachen, Germany."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Leemans, S.J.J., Fahland, D., and van der Aalst, W.M.P. (2013, January 24\u201328). Discovering Block-Structured Process Models from Event Logs\u2014A Constructive Approach. Proceedings of the Application and Theory of Petri Nets and Concurrency\u201434th International Conference, Milan, Italy.","DOI":"10.1007\/978-3-642-38697-8_17"},{"key":"ref_13","unstructured":"Verbeek, E., Buijs, J.C.A.M., van Dongen, B.F., and van der Aalst, W.M.P. (2010, January 14\u201316). ProM 6: The Process Mining Toolkit. Proceedings of the Business Process Management 2010 Demonstration Track, Hoboken, NJ, USA."},{"key":"ref_14","unstructured":"van Dongen, B.F. (2012). BPI Challenge 2012, Eindhoven University of Technology."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1142\/S0218126698000043","article-title":"The Application of Petri Nets to Workflow Management","volume":"8","year":"1998","journal-title":"J. Circuits Syst. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/5.24143","article-title":"Petri nets: Properties, analysis and applications","volume":"77","author":"Murata","year":"1989","journal-title":"Proc. IEEE"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"van der Aalst, W.M.P. (2000, January 19). Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques. Proceedings of the Business Process Management, Models, Techniques, and Empirical Studies, Berlin, Germany.","DOI":"10.1007\/3-540-45594-9_11"},{"key":"ref_18","unstructured":"Jouck, T., and Depaire, B. (2016, January 21). PTandLogGenerator: A Generator for Artificial Event Data. Proceedings of the BPM Demo Track 2016, Rio de Janeiro, Brazil."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1007\/s12599-018-0541-5","article-title":"Generating Artificial Data for Empirical Analysis of Control-flow Discovery Algorithms\u2014A Process Tree and Log Generator","volume":"61","author":"Jouck","year":"2019","journal-title":"Bus. Inf. Syst. Eng."},{"key":"ref_20","unstructured":"Leemans, S. (2017). Robust Process Mining with Guarantees. [Ph.D. Thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology]."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1109\/TKDE.2018.2841877","article-title":"Automated Discovery of Process Models from Event Logs: Review and Benchmark","volume":"31","author":"Augusto","year":"2019","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Carmona, J., van Dongen, B.F., Solti, A., and Weidlich, M. (2018). Conformance Checking\u2014Relating Processes and Models, Springer.","DOI":"10.1007\/978-3-319-99414-7"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.infsof.2006.11.004","article-title":"Translating unstructured workflow processes to readable BPEL: Theory and implementation","volume":"50","author":"Lassen","year":"2008","journal-title":"Inf. Softw. Technol."},{"key":"ref_24","unstructured":"Lassen, K.B., and van der Aalst, W.M.P. (November, January 29). WorkflowNet2BPEL4WS: A Tool for Translating Unstructured Workflow Processes to Readable BPEL. Proceedings of the CoopIS, DOA, GADA, and ODBASE, OTM Confederated International Conferences, Montpellier, France."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1016\/j.datak.2009.02.015","article-title":"The refined process structure tree","volume":"68","author":"Vanhatalo","year":"2009","journal-title":"Data Knowl. Eng."},{"key":"ref_26","unstructured":"Polyvyanyy, A., Vanhatalo, J., and V\u00f6lzer, H. (2010, January 16\u201317). Simplified Computation and Generalization of the Refined Process Structure Tree. Proceedings of the WS-FM 2010, Hoboken, NJ, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Polyvyanyy, A., Garc\u00eda-Ba\u00f1uelos, L., and Dumas, M. (2010, January 13\u201316). Structuring Acyclic Process Models. Proceedings of the Business Process Management\u20148th International Conference, Hoboken, NJ, USA.","DOI":"10.1007\/978-3-642-15618-2_20"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1016\/j.is.2011.10.005","article-title":"Structuring acyclic process models","volume":"37","author":"Polyvyanyy","year":"2012","journal-title":"Inf. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1093\/comjnl\/bxs126","article-title":"Maximal Structuring of Acyclic Process Models","volume":"57","author":"Polyvyanyy","year":"2014","journal-title":"Comput. J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"399","DOI":"10.3233\/FI-2011-614","article-title":"Causal Behavioural Profiles\u2014Efficient Computation, Applications, and Evaluation","volume":"113","author":"Weidlich","year":"2011","journal-title":"Fundam. Inform."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Polyvyanyy, A., Weidlich, M., and Weske, M. (2010, January 25\u201329). The Biconnected Verification of Workflow Nets. Proceedings of the On the Move to Meaningful Internet Systems: OTM 2010\u2014Confederated International Conferences: CoopIS, IS, DOA and ODBASE, Hersonissos, Crete, Greece.","DOI":"10.1007\/978-3-642-16934-2_29"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0022-0000(83)90029-6","article-title":"A Method for Stepwise Refinement and Abstraction of Petri Nets","volume":"27","author":"Suzuki","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Esparza, J., and Hoffmann, P. (2016, January 2\u20138). Reduction Rules for Colored Workflow Nets. Proceedings of the Fundamental Approaches to Software Engineering\u201419th International Conference, FASE 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, Eindhoven, The Netherlands.","DOI":"10.1007\/978-3-662-49665-7_20"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.peva.2017.09.006","article-title":"Polynomial analysis algorithms for free choice Probabilistic Workflow Nets","volume":"117","author":"Esparza","year":"2017","journal-title":"Perform. Evaluation"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/279\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:28:19Z","timestamp":1760178499000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,2]]},"references-count":34,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["a13110279"],"URL":"https:\/\/doi.org\/10.3390\/a13110279","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202009.0737.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,2]]}}}