Introduction

Enterprises model their business processes for various purposes, e.g., documentation of business operations, staff planning, or process automation. As a consequence, process models might show deviations in terms of level of detail, control flow, and activity labels, even if they capture a common real-world process.

In order to detect inconsistencies between related process models, their commonalities and differences have to be identified [1]. As a first step, this requires the identification of activities that correspond to each other. Note that this might not imply semantic equivalence of the activities (e.g., 'Get Quote' might correspond to 'Enter Quote Details' although both activities are not semantically equivalent). Such correspondences can be elementary 1:1 matches between activities, or complex 1:n (or even n:m) matches due to refinements of activities. Correspondences may stem from a system analyst inspecting the models or from automatic matching, cf., [2,3]. As a second step, the behavioural equivalence of process models aligned by correspondences is assessed to detect inconsistencies and guide process harmonisation efforts.

Although not in a straight-forward manner, existing notions of behaviour inheritance might be applied for this purpose even in the presence of complex correspondences between two process models. However, we argue that certain violations of behaviour inheritance can be detected structurally. In this paper, we show that a structural decomposition of a sound free-choice WF-system might provide valuable hints at correspondences that violate behaviour inheritance. In particular, we focus on the notion of projection inheritance in the context of trace semantics, i.e., an adapted version of the trace equivalence criterion [4].

C1

C2 C3 C4

Load Template (5) Get Project Details (A) Fig. 1. Two exemplary process models, (a) focussing on the organisational perspective, (b) depicting the respective technical process, along with complex correspondences Fig. 1 illustrates the problem addressed by this paper using two Petri nets that model a project planning process. Model (a) assumes an organisational perspective, whereas (b) shows the processing according to a supporting IT system. There are four complex correspondences highlighted using dash-dotted lines. Note that τ -transitions are never considered to be part of any correspondence. Clearly, the execution dependencies for transitions that are part of correspondences are not always consistent in both models. For instance, transitions D and H might be enabled concurrently in model (a), whereas their corresponding transitions, e.g., 5 and 7, are causally related in model (b). The question of whether and how such inconsistencies can be detected structurally is addressed in this paper.

The remainder of this paper is structured as follows. Section 2 gives preliminaries for our work. We discuss structural properties of correspondences in Section 3. Section 4 elaborates on behavioural analysis of correspondences. Finally, Section 5 reviews related work, before Section 6 concludes the paper.

Preliminaries

We recall basic definitions for workflow (WF-) systems based on [5,6]. A net is a tuple N = (P, T, F ) with P and T as finite disjoint sets of places and transitions, and F ⊆ (P × T ) ∪ (T × P ) as the flow relation. We write X = (P ∪ T ) for all nodes and F + for the transitive closure of F . For a node x ∈ X,

•x := {y ∈ X | (y, x) ∈ F }, x• := {y ∈ X | (x, y) ∈ F }, in N (x) := {(n, x) | n ∈ •x}, and out N (x) := {(x, n) | n ∈ x•}. A net N is free-choice, iff ∀ p ∈ P with |p • | > 1 holds •(p•) = {p}. N is conntected, if ∀ x 1 , x 2 ∈ X [ x 1 F + x 2 ∧ x 2 F + x 1 ]. A workflow (WF-) net is a net N = (P, T, F ),

such that there is exactly one place i ∈ P with •i = ∅, exactly one place o ∈ P with o• = ∅, and the short-circuit net N = (P, T ∪ {t c }, F ∪ {(o, t c ), (t c , i)}) is connected. M : P → N is a marking of N and M p denotes the marking that puts a token on p and no token elsewhere for a place p ∈ P . Given a WF-net N with M i as its initial marking, we refer to the tuple S = (N, M i ) as a WF-system and assume N to be defined always as N = (P, T, F ). We do not recall semantics for WF-systems but refer to [5,6]. (N, M i ) is sound, iff the short-circuit system (N , M i ) is live and bounded [7]. We apply the structural decomposition technique introduced as the RPST in [8] to parse a WF-system into a hierarchy of fragments with a single entry node and a single exit node. Then, the RPST is a containment hierarchy of canonical fragments of the system that can be computed in linear time.

Definition 1 (Fragments, RPST). Let N = (P, T, F ) be a WF-net with initial place i and final placeo. -A node x ∈ X of a connected subnet N = (P , T , F ) of a net N is a boundary node, if ∃ e ∈ in N (x) ∪ out N (x) [ e / ∈ F ]. If x is a boundary node, it is an entry of N , if in N (x) ∩ F = ∅ or out N (x) ⊆ F , or an exit of N , if out N (x) ∩ F = ∅ or in N (x) ⊆ F . -Any connected subnet ω of N , is a fragment, if it

has exactly two boundary nodes, one entry and one exit.

-A fragment ω = (P ω , T ω , F ω ) is canonical in a set of fragments Ω of N , iff ∀ γ = (P γ , T γ , F γ ) ∈ Ω [ ω = γ ⇒ (F ω ∩ F γ = ∅) ∨ (F ω ⊂ F γ ) ∨ (F γ ⊂ F ω ) ]. The RPST of N is a tuple R N = (Ω, χ, t), where:

-Ω is a set of all canonical fragments of N , χ : Ω → P(Ω) is a function that assigns to fragment its child fragments, t : Ω → {T, P, B, R} is a function that assigns a type to a fragment.

Fig. 2 shows the canonical fragments for one of the WF-systems of our example along with the corresponding RPST. Note that each canonical fragment can be classified as being either a trivial (T ) fragment (a single edge), a polygon (P ) fragment (a sequence of fragments), a bond (B) (fragment collection with common boundary nodes), or a rigid (R) fragment (any other structure).

Structural Properties of Correspondences

This section clarifies the notion of a correspondence between two WF-systems. Following on the terminology known from the domain of schema matching or ontology matching [9], a correspondence is defined by two sets of transitions of the WF-systems.

⊆ T . If T 1 ∼ T 2 then (T 1 , T 2 ) is referred to as a correspondence. (T 1 , T 2 ) is called elementary, iff |T 1 | = |T 2 | = 1

, and complex otherwise.

Further on, we discuss the structural relation between multiple correspondences between two systems by means of two structural properties. First, correspondences might be overlapping, i.e., they share a transition in at least one of the WFsystems.

Definition 3 (Overlapping Correspondences

). Let (N , M i ) and (N , M i ) be two WF-systems and

C 1 = (T 1 , T 2 ) and C 2 = (T 3 , T 4 ) two correspondences between them, such that T 1 , T 3 ⊆ T and T 2 , T 4 ⊆ T . C 1 and C 2 are called overlapping, iff T 1 ∩ T 3 = ∅ or T 2 ∩ T 4 = ∅.

Fig. 3. Pre-processing

Regarding the example in Fig. 1, we see that all correspondences are non-overlapping. Second, we provide an additional property for the structural relation between two correspondences, which is based on the RPST. Here, we have the assumption that all transitions that are part of a correspondence have a single incoming and single outgoing flow arc. If not, a behaviour preserving pre-processing is done, cf., Fig. 3. Note that the systems in Fig. 1 are pre-processed. The property requires that two correspondences are not overlapping in terms of their lowest enclosing fragments in the RPST.

Definition 4 (Structurally Independent Correspondences). Let (N , M i ) and (N , M i ) be two WF-systems, R N = (Ω , χ , t ) the RPST of N , and C 1 = (T 1 , T 2 ) and C 2 = (T 3 , T 4 ) with T 1 , T 3 ⊆ T and T 2 , T 4 ⊆ T two correspondences. C 1 and C 2 are structurally independent in N , iff |T 1 | = |T 3 | = 1 or ∀ ω = (P ω , T ω , F ω ) ∈ Ω [ T 1 ∩ T ω = ∅ ∧ T 3 ∩ T ω = ∅ ⇒ T 1 ⊆ T ω ∧ T 3 ⊆ T ω ].

Our example in Fig. 1 illustrates correspondences that are structurally independent in one or both systems. For instance, the pair of correspondences C1 and C2 is independent in model (a), as every fragment containing transition A and either B or C contains all three transitions, cf., Fig. 2. However, the very same pair of correspondences is not independent in model (b), as there is a bond fragment that represents a subnet comprising transitions 3, 4, and 5, but which does not contain transition 1. In contrast, C1 and C4 are an example for a pair of correspondences that are structurally independent in both models (a) and (b).

Behavioural Analysis of Correspondences

Based on the structural properties of correspondences introduced in the previous section, this section discusses behavioural analysis of correspondences. First, we elaborate on the behavioural ambiguity of overlapping correspondences. Second, the application of common notions of behaviour inheritance in the context of complex correspondences is discussed. Subsequently, we introduce heuristics to detect violations of behaviour inheritance for structurally independent correspondences.

Overlapping Correspondences

Overlapping Correspondences. Overlapping correspondences raise various questions regarding their intended meaning. That is, it is unclear whether an occurrence of a transition that is part of both overlapping correspondences should be considered for one or for both correspondences. For instance, consider the systems depicted in Fig. 4. Here, the trace A1, X in the lower system might correspond to both, the occurrence of transition A only, or the occurrence of both transitions, A and B, in the upper system. Thus, the semantic ambiguity of such overlapping correspondences has to be addressed as a prerequisite for any behavioural analysis.

Behaviour Inheritance. In order to judge about behaviour equivalence in the context of correspondences between process models, first and foremost, the treatment of transitions without counterparts has to be addressed. To this end, two notions of behaviour inheritance can be distinguished, i.e., protocol inheritance or projection inheritance, cf., [10,11]. That is, transitions in one model that are without counterpart in the second model are either blocked (protocol inheritance) or hidden (projection inheritance). Although these notions have been defined based on branching bisimulation, they can easily be transferred to trace-based behaviour analysis. It is worth to mention that the term inheritance is slightly misleading in our context as it implies a directed relation between two models (one model is a subclass of the other model). As illustrated by our example in Fig. 4, such a directed relation might not exist between aligned models.

The choice between protocol inheritance or projection inheritance is independent of the structural characteristics of the correspondences. However, we focus on projection inheritance in the context of this paper. In particular, this notions seems to be more appropriate when comparing models that focus on different modelling perspectives (e.g., organisational vs. technical) as intermediate process steps that are mandatory in one perspective may be without counterpart in the other model. For instance, transition F of model (a) in Fig. 1 is not part of any correspondence even though its execution is required for completion of process (a). Thus, any notion of protocol inheritance would be bound to failure.

In the general case, projection inheritance in terms of trace semantics between two models is assessed as follows. The language of both process models is checked for equivalence, when all correspondences are resolved. In case of 1:1 elementary correspondences this resolution is straightforward as an occurrence of one transition in one model corresponds to the occurrence of another transition in the other model. For the case of complex correspondences, this resolution involves a replacement of all valid subtraces involving the transitions of the correspondence in the one model with all valid subtraces comprising the corresponding transitions in the other model. Consider the example in Fig. 1 and neglect correspondence C2 and C3 for the time being. Then, the traces A, D and A, E in model (a) (all other transitions are hidden) would be rewritten as follows. According to the correspondences, an occurrence of A is replaced by the subtraces 1, 3, 4 or 1, 4, 3, while the subtraces D and E are replaced by an occurrence of transition 7. That yields the two traces 1, 3, 4, 7 and 1, 4, 3, 7. As both traces described the language of model (b) when taking only transitions of correspondences C1 and C4 into account, we conclude that both correspondences do not violate projection inheritance. Note that during this analysis, the interleaving of transitions belonging to different correspondences has to be considered. Based thereon, each pair of correspondences can be assessed. If all correspondences show pairwise projection inheritance, projection inheritance for the two models and their alignment in terms of a set of correspondences can be concluded.

Structural Characterisation of Violations. While the aforementioned approach of comparing the set of all resolved traces can always be taken, violations of projection inheritance may already be discovered using a heuristic approach. It uses the RPST decomposition technique for sound free-choice WF-systems and is applicable for correspondences that are structurally independent in both systems (cf., Section 3). In previous work, we showed that the RPST of sound free-choice WF-systems can be annotated with behavioural details. That is, bond fragments are either transition bordered or place bordered, but there cannot be a mix of place and transition boundary nodes [12]. The former represents a parallel block, whereas the latter represents either an exclusive block or a loop fragment.

This information, in turn, can be leveraged to identify violations of projection inheritance that are induced by correspondences. Given two correspondences we proceed as follows.

1. Determine the lowest common ancestor (LCA) in the respective RPST of all trivial T fragments for which the entry node is a transition aligned by one of the two correspondences. Derive the LCA in both models. 2. Compare the type of the LCA fragments.

-If one LCA fragment is of type P , the other LCA fragment has to be of type P as well and the order of the respective child fragments (transitively) containing all T fragments of the correspondences has to coincide in both LCA fragments. -If one LCA fragment is of type B and not cyclic, the other LCA fragment has to be of type B and acyclic as well. In addition, the fragments are either both place bordered or both transition bordered. -If one LCA fragment is of type B and cyclic, the other LCA fragment has to be of type B and cyclic as well. This observation can be explained as follows. As both correspondences are structurally independent, the LCA of all T fragments that are related to the transitions of the correspondence must have at least two children, one (transitively) containing all T fragments related to one correspondence and the other one (transitively) containing all T fragments related to the other correspondence. Therefore, the type of the LCA induces a constraint on the potential order of occurrence between all transitions of one correspondence and all transitions of the other correspondence. This constraint has to hold in the second model as well. For instance, if there is a sequential order (LCA is P fragment) between the respective T fragments (and, therefore, the transitions) of the two correspondences in one model, there cannot be a potential concurrent enabling (LCA is B fragment that is transition bordered) of the corresponding transitions in the other model. Such a setting will never show projection inheritance. It is important to see two limitations of this approach. On the one hand, conclusions cannot be drawn, if one of the two LCAs is a rigid (R) fragment, as the constraints on the order of potential execution cannot be derived directly. On the other hand, this check is solely a heuristic that formulates a necessary, but not a sufficient condition for a violation of projection inheritance. Even if the type of the LCA is equal, projection inheritance might be violated by the two correspondences. For instance, if both LCAs are of type P , it might still be the case that the occurrence of all transitions of one correspondence is optional in one model, whereas it is mandatory in the other model.

Besides (C1, C2) and (C1, C3), all pairs of correspondences in Fig. 1 are structurally independent in both models, such that the types of the respective LCA fragments can be compared. That, in turn, yields the following result. For the pairs (C1, C4), (C2, C3), and (C2, C4) the LCA fragments show a consistent type in both models. In contrast, for correspondence (C3, C4) the LCA fragment is of type B (transition bordered) in model (a) and of type P in model (b). Thus, the structural analysis revealed that correspondences C3 and C4 violate projection inheritance between both models. Transitions of both correspondences might be enabled concurrently in model (a), which is not possible in model (b).

Regarding correspondences that are not structurally independent in both systems, we already discussed the case of correspondences C1 and C2 of our example in Fig. 1. These correspondences obviously violate projection inheritance. However, our example also illustrates that correspondences that are structurally dependent do not necessarily lead to violations. Consider, for instance, correspondences C1 and C3, which are not structurally independent in model (b), due to fragments that represent subnets containing transitions 3, 4, 5, 6, but not 1. Nevertheless, the order between all transitions of correspondence C1 and C3 as imposed by model (a) is also reflected in model (b). Albeit beyond the scope of this discussion, we foresee that necessary conditions for violations can also be specified for the case of correspondences that are not structurally independent.

Related Work

We already discussed related work in the field of behaviour equivalence [4] and behaviour inheritance [10,11]. Further on, work on trace-based assessment of similarity is related to our work. For instance, the set n-grams of possible traces two models can be compared [13]. In other work, a trace is replayed in a model and the number of valid replay steps is leveraged for measuring similarity [14].

Moreover, the assessment of behaviour inheritance in the presence of complex correspondences is related to work on behaviour preserving model refinements, see [15] for a thorough survey. A transition refinement is defined by replacing a transition with a block-structured refinement net with a dedicated set of initial and final transitions. However, other approaches allow refinement nets to also show so-called distributed input or distributed output places [15].

In this paper, we addressed the challenge of assessing behaviour equivalence for process models aligned by complex correspondences. In particular, we discussed how the notion of behaviour inheritance can be applied for complex correspondences and also introduced necessary conditions for violations of this notion by a pair of correspondences based on structural decomposition techniques for sound free-choice workflow systems.

As a next step, the discussed application of behaviour inheritance in the context of complex correspondences needs to be formalised. In addition, we want to further investigate the structural characterisation of correspondences and their relation to the notions of behaviour inheritance. Here, the goal would be the specification of structural characterisations that are not only a necessary, but also a sufficient condition for a violation of behaviour inheritance.