Translating Workflow Nets into the Partially Ordered Workflow Language

Humam Kourani, Gyunam Park, Wil M. P. Van Der Aalst
June, 2025
PDF Cite DOI

Abstract

Process discovery aims to automatically derive process models from event logs, enabling organizations to analyze and improve their operational processes. Inductive mining algorithms, while prioritizing soundness and efficiency through hierarchical modeling languages, often impose a strict block-structured representation. This limits their ability to accurately capture the complexities of real-world processes. While recent advancements like the Partially Ordered Workflow Language (POWL) have addressed the block-structure limitation for concurrency, a significant gap remains in effectively modeling non-block-structured decision points. In this paper, we bridge this gap by proposing an extension of POWL to handle non-block-structured decisions through the introduction of choice graphs. Choice graphs offer a structured yet flexible approach to model complex decision logic within the hierarchical framework of POWL. We present an inductive mining discovery algorithm that uses our extension and preserves the quality guarantees of the inductive mining framework. Our experimental evaluation demonstrates that the discovered models, enriched with choice graphs, more precisely represent the complex decision-making behavior found in real-world processes, without compromising the high scalability inherent in inductive mining techniques.

Type
Conference paper
Publication
Application and Theory of Petri Nets and Concurrency - 46th International Conference, PETRI NETS 2025, Paris, France, June 22-27, 2025, Proceedings

Practical problem

Organizations document and analyze their processes in established notations such as Petri nets (specifically workflow nets) and the Business Process Model and Notation (BPMN), and the tools they rely on expect those formats. These notations, however, give no guarantee that a model is free of deadlocks or other anomalies, and their flat graph structure makes large models hard for people to read and for algorithms to exploit. The Partially Ordered Workflow Language (POWL) is a hierarchical notation that fixes both issues and already powers process discovery and modeling from text, but adopting it would mean replacing existing models and tools. Turning a POWL model into a workflow net is easy; going the other way, so that existing models can be reused, had no algorithm with formal guarantees.

Research questions

  1. How can a safe and sound workflow net be decomposed and translated into a POWL model whose language equals that of the net?
  2. For which class of workflow nets does such a translation always succeed, and how does the approach scale to large models compared with existing workflow-net-to-process-tree conversion?

Contributions

  • A recursive top-down algorithm that identifies exclusive-choice, loop and partial-order patterns in a safe and sound workflow net and projects the net onto sub-nets for further decomposition.
  • Formal definitions of the three patterns and their projections, plus reduction rules (explicit decision-point places, self-loop handling) that widen the set of nets the algorithm accepts.
  • Proofs that each projection preserves safeness and soundness and that each pattern preserves language, yielding a correctness theorem for every produced POWL model.
  • Defines the class of semi-block-structured workflow nets, which contains equivalents of all POWL models, and proves the algorithm is complete on that class.
  • An open-source implementation (GitHub humam-kourani/WF-net-to-POWL), also integrated into the ProMoAI tool, evaluated against the PM4Py-based workflow-net-to-process-tree converter.

Key findings

  • Every POWL model produced by the algorithm has exactly the language of the input workflow net (Theorem 1, by structural induction over the XOR, loop and partial-order cases).
  • The algorithm converts every semi-block-structured workflow net, a class that strictly contains block-structured nets and sound marked-graph workflow nets and sits inside sound free-choice nets (Theorem 2).
  • On 1000 generated workflow nets with 21 to 370 transitions and 15 to 305 places, all are converted in 0.002 to 2.48 seconds, versus 0.013 to 126 seconds for the process-tree converter.
  • On the 20 ground-truth workflow nets of a process-modeling benchmark, the algorithm converts all 20, whereas the process-tree converter handles only 17.
  • The algorithm returns null for nets whose language has no POWL equivalent, e.g. free-choice nets with non-block-structured decision points or long-term dependencies between choices.