POWL: Partially Ordered Workflow Language (Extended Abstract)

1 Introduction

Process modeling is essential for understanding, analyzing, and optimizing business operations. Process models, which can be manually created or automatically discovered from data, provide insights into process execution. By highlighting issues and bottlenecks within processes, process models enable organizations to automate and optimize their processes.

Different process modeling languages are employed in the field of business process management. Petri nets, especially their subclass Workflow nets (WF-nets), exemplify a widely recognized formal notation for process modeling [van Hee et al., 2013]. WF-nets may encounter behavioral quality issues, e.g., it is possible to generate WF-nets with unreachable parts. In contrast, process trees [Leemans, 2022] offer a hierarchical modeling approach ensuring soundness by design, albeit limited to representing hierarchical behavior.

To illustrate this, consider the process of an online shopping transaction illustrated as a WF-nets in Figure 1a. In this process, the item selection (activity b) and choosing a payment method (c) can happen in any order. After item selection (b), the user picks a free reward (f), a step dependent on the total purchase value yet independent from the payment activities (c, d, and e). A process tree, as demonstrated in Figure Figure 1b, uses control-flow operators like →, ×, +, and ⟲ to represent sequential activities, exclusive choices, concurrency, and loops, respectively. Process trees struggle to accurately model the complex dependencies between b, c, d, e, and f as such non-hierarchical dependencies cannot be precisely captured using control-flow operators. For example, the tree in Figure 1b allows for selecting the reward and/or completing the payment before selecting the items.

∗This extended abstract is based on the paper "POWL: Partially Ordered Workflow Language" presented at the 21st International Conference on Business Process Management (BPM 2023).

Partial orders provide an effective and compact representation of the execution order of activities within processes. In partial order, activities are assumed to be concurrent (i.e., can be executed in any order) unless order restrictions are explicitly defined. For instance, Figure 1c shows a graph representation of a partial order. The edge (b → f) indicates that selecting the reward is only possible after completing the item selection, while selecting the reward (f) and setting the payment method (c) can be executed in any order as they are not connected in the graph. While partial order are able to model the non-hierarchical dependencies between b, c, d, e, and f in our process, they fall short in representing cyclic behavior (in our example, the loop of delivering and returning items) as a partial order is irreflexive. Moreover, partial orders cannot describe choice behavior (such as the choice between payment and setting up an installment plan in our example) since all activities in a partial order are assumed to be executed."

The introduction of Partially Ordered Workflow Language (POWL) aims to integrate the best of hierarchical modeling languages with the flexibility of partial orders. A POWL model is a hierarchical model generated by combining submodels either as partial orders or using control-flow operators. Figure 1d shows a POWL model that precisely describes the behavior of our example process. This model captures the complex dependencies between b, c, {d, e}, and f as a partial order, and at the same time, it uses the control-flow operators × and ⟲ the model the choice of d and e and the and the loop between g and h respectively. Despite their support for partial orders, POWL models are guaranteed to be sound by construction, which makes POWL particularly suitable for the automated discovery of process models from data.

The remainder of the paper is structured as follows. We discuss related work in Section 2, and then POWL is introduced in Section 3. In Section 4, we present an approach that demonstrates the feasibility of employing POWL in process discovery, and we evaluate this discovery approach on reallife data in Section 5. Finally, Section 6 concludes the paper.

2 RelatedWork

The POWL language is introduced in [Kourani and van Zelst, 2023], and significant advancements in the discovery of POWL models are reported in [Kourani et al., 2023]. Furthermore, [Kourani et al., 2024a; Kourani et al., 2024b] investigate leveraging the synergy between POWL and large language models, highlighting the capability of POWL in facilitating process modeling through innovative artificial intelligence techniques.

A comprehensive overview of various languages utilized for process modeling is provided in [Schnieders et al., 2004]. Efforts to combine diverse modeling notations have led to innovative hybrid models. For instance, [van der Aalst et al., 2023] describes a hybrid Petri net featuring formal and informal constraints between activities, while [Slaats et al., 2016] explores combining imperative and declarative models.

A survey on the application of partial orders in data representation and process modeling is provided in [Leemans et al., 2022]. In [Mannila et al., 1997; Leemans and van der Aalst, 2014], the discovery of frequent partially ordered sets of events is explored. Prime event structures are defined in

[Nielsen et al., 1981] as partially ordered graphs extended with conflict relations, and [Dumas and Garc´ıa-Ba˜nuelos, 2015] proposes approaches for the discovery of prime event structures. In [Mokhov and Yakovlev, 2010], Conditional partial order graphs are defined as families of partial orders, and they are employed in process discovery in [Mokhov and Carmona, 2015]. Both prime event structures and conditional partial order graphs address the challenge of modeling choices within partial orders, yet the integration of cyclic behavior remains a challenge for these notations. Lastly, [Ouyang et al., 2007] introduces BPEL as a flow language that combines web service components through control-flow constructs, and it additionally supports adding order constraints between parallel components. Despite BPEL's advanced capabilities, its complexity positions it closer to a programming tool for web service implementation rather than a user-friendly modeling language [van der Aalst et al., 2005].

3 POWL Language

In this section, we introduce POWL and we illustrate an approach for transforming POWL models into sound WF-nets.

Notation Let ≺ ⊆ X × X be a 2-ary relation over a set X. For (x1, x2) ∈ X × X, we write x1≺x2 to denote that (x1, x2) ∈ ≺, and we write x1⊀x2 to denote that (x1, x2) /∈ ≺. We call ≺ a partial order if it is irreflexive (i.e., x⊀x for all x ∈ X ) and transitive (i.e., if x1≺x2 and x2≺x3, then x1≺x3). Irreflexivity and transitivity imply asymmetry (i.e., if x1≺x2, then x2⊀x1). We refer to ρ = (X,≺) as a partially ordered set (poset). We use Σ to denote the universe of activities, and we use τ /∈ Σ to denote the silent activity (also called the invisible activity), which is used to model skippable parts and self-loops [van der Aalst, 2016].

A POWL model represents a process as a partially ordered graph, augmented with control-flow operators to depict choices and loops. We define three types of POWL models. First, the base case comprises single activities. For the second type, the control-flow operators × and ⟲ are employed to combine sub-models into a larger POWL model. We use × to model an exclusive choice of POWL models, and we use ⟲ to model a do-redo loop of two POWL models: the first submodel (do-part) is executed first, and every execution of the second sub-model (redo-part) invokes a subsequent execution of the do-part. For the third type of POWL models, submodels are combined as a partially ordered set. Unconnected nodes in a partial order indicate concurrency, while connections between nodes represent sequential dependencies.

Definition 1 (POWL Model). A POWL model is defined recursively as follows:

• Any activity a ∈ Σ ∪ {τ} is a POWL model.
• Let ψ1 and ψ2 be two POWL models. ⟲(ψ1, ψ2) is a POWL model.
• Let P = {ψ1, ..., ψn} be a set of n ≥ 2 POWL models.
• ×(ψ1, ..., ψn) is a POWL model.
• A poset ρ = (P, ≺) is a POWL model.

For the formal semantics of POWL models, we refer to [Kourani and van Zelst, 2023]. POWL models can be recursively transformed into WF-nets, and the generated workflow net is guaranteed to be sound [Kourani and van Zelst, 2023].

4 Discovery of POWLModels

This section explores the practical application of POWL in the realm of process discovery by adapting the inductive miner [Leemans, 2022] to generate POWL models.

4.1 Event Log

In the context of process discovery, data is assumed to be presented as an event log. We define an event log as a multi-set comprising sequences of activities, called traces, that encapsulate the execution flow of different process instances. We write an event log as a multi-set L = [σ1 f1 , ..., σn fn ] where fi refers to the frequency of the trace σi for 1 ≤ i ≤ n. For example, L1 = [⟨a, b, c⟩3 , ⟨a, b, d⟩2 ] is an event log that comprises the trace ⟨a, b, c⟩ with a frequency of 3 and another trace ⟨a, b, d⟩ with a frequency of 2.

4.2 Inductive Miner

The inductive miner [Leemans, 2022] is an approach widely used for process discovery due to its high scalability and formal guarantees. These guarantees include soundness, rediscoverability of specific structures, and perfect fitness (i.e., all behaviors observed in the event log are included within the model's language).

Employing a recursive, top-down strategy, the algorithm seeks a cut by identifying a behavioral pattern in the event log and partitioning the activities accordingly. Recognizing four distinct cuts corresponding to the process tree operators, it recursively constructs a process tree that models the identified patterns. Subsequent to a cut detection, the event log is projected onto the activity partitions, generating sub-logs, and the algorithm is recursively applied on the sub-logs until reaching a base case. A base case, defined as a log containing a single activity, trivially translates into a process tree node.

In scenarios where neither a base case nor a cut is detected, the Inductive Miner employs a fall-through function. This function always returns a cut, potentially encompassing behavior more general than what is observed in the event log, yet ensuring the continuity of recursion. For a detailed exposition of the inductive miner, we refer to [Leemans, 2022].

4.3 Mining for Partial Orders

As illustrated in Figure 2, we adapt the inductive miner to discover POWL models by additionally mining for partial orders. This additional step is performed after no standard process tree cuts are discovered and before invoking the fallthrough function. Our discovery approach involves generating candidate partial orders over different partitionings of activities and validating them through predefined rules to ensure a high conformance between the partial order and the input event log. Upon identifying a valid partial order, the event log is accordingly projected, and the recursive procedure progresses with the derived sub-logs. In the absence of a valid order, the fall-through function is triggered. Note that in cases where a sequence or concurrency cut is detected, the cut is transformed into a partial order as POWL models do not support the operators → and +. For more details on the partial order cut detection step and the applied validity rules, we refer to [Kourani and van Zelst, 2023]. Note that this discovery approach was extended in [Kourani et al., 2023] to improve scalability on large data sets.

Figure 3 shows an example application of our discovery approach on an event log. In the first iteration, a partial order is discovered, and the event log is projected on the subsets of activities {a, b}, {c}, and {d}. Afterwards, a choice cut between the activities a and b is detected.

5 Evaluation

The implementation of our approach for discovering POWL models is available in the open-source Python library PM4Py (http://pm4py.org/). We evaluated our approach (IMP) on real-life event logs, and we compared the resulting models with the models discovered by the base inductive miner (IM).

Setup

We transformed all discovered models into WF-nets in order to enable the assessment of their quality using traditional conformance-checking techniques [Carmona et al., 2018]. For each model, we computed three conformance-checking scores: fitness, precision, and simplicity. Fitness [Berti and van der Aalst, 2019] measures the extent to which the observed behavior in the event log can be reproduced by the model; precision [Munoz-Gama and Carmona, 2010] assesses how accurately the model avoids allowing behavior that is not seen in the event log, ensuring that the model does not overgeneralize; and simplicity evaluates the structural complexity of the model based on the average number of arcs per node.

Our evaluation encompasses several real-life event logs, including a sepsis cases log from a hospital [Mannhardt, 2016], a road traffic fine management system log [de Leoni and Mannhardt, 2015], a hospital billing system log [Mannhardt, 2017], and the BPI Challenge logs from 2017 to 2020 [van Dongen, 2017; van Dongen and Borchert, 2018; van Dongen, 2019; van Dongen, 2020]. The logs are pre-filtered to retain the most frequent activities, capped at 8 and 12 activities.

Results

Table 1 reports the discovery time and conformance-checking scores for all models. We omit the fitness values as all models achieved a fitness of 1 due to the perfect fitness guarantee both IM and IMP provide.

On one hand, IMP demonstrated improved time performance compared to IM in certain scenarios (e.g., BPI Challenge 2017). Conversely, IMP was more time-intensive in other instances. For example, both approaches required less than 1 second for the BPI Challenge 2020-3 log of 8 activities, while the time increased to 280 seconds for IMP with the log of 12 activities. This highlights how increasing the number of activities can significantly degrade time performance. These findings were expected since IMP employs a brute force method to generate and validate candidate partial orders. Note that efforts to address this scalability concern were made in [Kourani et al., 2023].

Overall, IMP yielded simpler models than IM. In 18 cases, the model discovered by IMP achieved a higher simplicity score compared to only one instance where IM led to a simpler model. Similarly, IMP generally obtained higher precision values. For example, the model discovered by IMP for the BPI Challenge 2017 event log with 8 activities achieved a precision of 0.68, whereas IM's model achieved 0.37. In this scenario, the support of partial orders enabled IMP to identify local dependencies between activities that cannot be captured in process trees. Although IMP generally produced more precise models compared to IM (for 11 logs), there were two exceptions. For instance, in the BPI Challenge 2018 event log with 8 activities, the precision decreased from 0.35 to 0.32. This case exemplifies where invoking the fall-through function yielded better results than detecting a partial order. To continue the recursion, the fall-through function returned a concurrency cut between an activity occurring at most once in every trace and the remaining activities.

6 Conclusion

This paper presents the Partially Order Workflow Language (POWL), a novel language for business process modeling. A POWL model is a hierarchical model generated by combining sub-models either as partial orders or using standard control-flow operators for modeling choice and loop structures. Moreover, we propose an approach that demonstrates the feasibility of utilizing POWL in process discovery, and we evaluate our approach on real-life event logs. The evaluation showcases the ability of POWL to uncover complex process structures unattainable with traditional hierarchical modeling languages.