This paper is concerned with the discovery of models of distributed processes from event logs under the assumption that an algorithm for the discovery of the component models is given. We use Enterprise nets to model local processes, while Industry nets are compositions of Enterprise nets which interact through asynchronous message passing. First, we investigate the relation between the behaviour of Enterprise nets and that of Industry nets and formalise the (causal) structure of global (Industry net) behaviour in terms of a partial order derived from the message passing. Next, we demonstrate how to leverage existing algorithms for the discovery of workflow nets to discover Enterprise nets and how to combine these into an Industry net. Using the results on the structure of the global behaviour, we relate the behaviour of the Industry net thus discovered to the behaviour of the Enterprise nets and show how fitness of the Enterprise nets (the event log provided as input is included in the behaviour of the discovered net) is preserved as fitness of the Industry net.
Industry nets have been introduced in [
Business process modelling and process mining are nowadays very active
research areas and there are many approaches both to process discovery and
conformance checking (see, eg., [
In order to compare the given global behaviour with the behaviour (the firing sequences) of the Industry net, we first investigate, after a preliminary section, in Sections 3, 4, and 5, the relation between the behaviour of an Industry net and the firing sequences of its Enterprise nets. As a consequence of the asynchronous set-up, every sequence that can be executed by an Industry net is also locally executable (ignoring the actions of other components) by each of its Enterprise nets. To describe the converse relationship, we formulate a prefix property that identifies those action sequences that can be executed by an Industry net whenever they are locally executable in all component Enterprise nets. Furthermore, by explicitly assigning occurrences of output actions to (dependent) occurrences of input actions, we can associate with each sequence with the prefix property, a labelled partial order reflecting the necessary ordering of action occurrences in this sequence. All linearisations of this labelled partial order are also firing sequences of the Industry net. We show that, in case the input/output relation is based on a FIFO relation, the set of these linearisations is maximal. In Section 6, we demonstrate how to leverage existing process discovery algorithms to the discovery of Industry nets. Then we argue, based on the results from the earlier sections, how fitness of the nets delivered by the original algorithm (the event log provided as input is included in the behaviour of the discovered net) guarantees the fitness of the distributed model. Section 7 concludes the paper and briefly considers related work.
Due to the page limit, this paper has no proofs. We provide, however, examples, explanations, and lemmas to clarify our statements and results. 2
N = {0, 1, 2, . . .} is the set of natural numbers including 0. For n ∈ N, we set [n] = {1, 2, 3, . . . , n} and if n = 0, then [n] = ∅. By A ] B we denote the union of disjoint sets A and B. Given a partial order R ⊆ A × A, we refer to a total order R0 ⊆ A × A such that R ⊆ R0, as a linearisation of R.
An alphabet is a finite, non-empty, set of symbols. Let Σ be an alphabet. A word over Σ is a sequence w = a1 · · · an, with n ≥ 0 and ai ∈ Σ, for all i ∈ [n]; we refer to n as the length of w, denoted by |w|. If n = 0 then w is the empty word denoted by λ. Note that |λ| = 0. The set of all words over Σ is denoted as Σ∗. Any subset of Σ∗ is a language (over Σ). It is often convenient to consider a word w = a1 · · · an as a function w : [|w|] → Σ, defined by w(i) = ai for all i ∈ [n]. The alphabet of w is alph(w) = {w(i) | i ∈ [n]}. Hence alph(λ) = ∅. For a language L, Alph(L) = S{alph(w) | w ∈ L} is the set of all symbols that occur in the words of L. If a word w is a concatenation of words v1 and v2, i.e., w = v1v2, then v1 is said to be a prefix of w. The number of occurrences of symbol a ∈ Σ in a word w ∈ Σ∗ is defined as #a(w) = |{i | w(i) = a})| and the set of occurrences of w is occ(w) = {(a, i) | a ∈ alph(w) ∧ 1 ≤ i ≤ #a(w)}. In addition, we allocate a position with each occurrence of w through the function posw : occ(w) → [|w|] as follows: for all (a, i) ∈ occ(w), posw((a, i)) = k if w(k) = a and #a(w(1) · · · w(k)) = i. For a subset Δ of Σ, the projection of Σ∗ on Δ∗ is a function projΣ,Δ : Σ∗ → Δ∗, defined by projΣ,Δ(a) = a if a ∈ Δ, and projΣ,Δ(a) = λ otherwise; furthermore projΣ,Δ(wa) = projΣ,Δ(w)projΣ,Δ(a) whenever w ∈ Σ∗ and a ∈ Σ. We omit the subscript Σ if it is clear from the context and thus write projΔ(w) instead of projΣ,Δ(w).
Petri nets A Petri net is a triple N = (P, T, F ), where P is a finite set of places, T is a finite non-empty set of transitions such that P ∩ T = ∅, and F ⊆ (P × T ) ∪ (T × P ) is a set of arcs.
Let N = (P, T, F ) be a Petri net. If N 0 = (P 0, T 0, F 0) is a Petri net such that
P ∪ T and P 0 ∪ T 0 have no elements in common, then N and N 0 are disjoint.
Let x ∈ P ∪ T . Then •x = {y | (y, x) ∈ F } and x• = {y | (x, y) ∈ F } are
the preset and the postset, respectively, of x (in N ). A marking μ of N is a
function μ : P → N. Let t ∈ T and μ a marking of N . Then t is enabled at μ
if μ(p) > 0 for all p ∈ •t. If t is enabled at μ, it may occur, and thus lead to
a new marking μ0 of N , denoted μ →−tN μ0, with μ0(p) = μ(p) − 1 whenever
p ∈ •t\t•; μ0(p) = μ(p)+1 whenever p ∈ t• \•t; and μ0(p) = μ(p) otherwise.
We extend the notation μ →−tN μ0 to sequences w ∈ T ∗ as follows1: μ −→λN μ
wt
for all μ; and μ −→N μ0 for markings μ, μ0 of N , w ∈ T ∗ and t ∈ T ,
whenever there is a marking μ00 such that μ −→N μ00 and μ00 →−tN μ0. If
w
μ −→wN μ0, for some w ∈ T ∗, we say that μ0 is reachable from μ (in N ). The
1 We thus view T as an alphabet of action symbols.
language L(N, μ) = {w ∈ T ∗ | μ −→wN μ0 for some marking μ0} consists of
all possible firing sequences of N from μ. A place p ∈ P is a source place of
N if •p = ∅ and it is a sink place of N if p• = ∅. The marking μ of N such
that, for all p ∈ P , μ(p) = 1 if p is a source place and μ(p) = 0 otherwise,
is the default initial marking of N . If μ is the default initial marking of N ,
we may write L(N ) to denote L(N, μ) and refer to it as the language of N .
A workflow net (see [
Enterprise nets and Industry nets We recall the definitions of
Enterprise and Industry nets from [
We let M denote the set of message types fixed throughout this paper. Definition 1. An Enterprise net is a tuple E = (P, [Tint, Tinp, Tout], F, M ) such that Tint, Tinp, and Tout are mutually disjoint sets; Tint is the set of internal transitions of E , Tinp its set of input transitions, and Tout its set of output transitions; furthermore, the underlying Petri net of E , und(E ) = (P, Tint ] Tinp ] Tout, F ), is a Petri net with exactly one source place; finally M : Tinp ∪ Tout → M is the communication function of E . tu Given an Enterprise net E , L(E ) = L(und(E )) is the language of E . Note that E-nets, like workflow nets, have a single source place; no further restrictions are imposed on the underlying net.
Composing E-nets yields an Industry-net (or I-net, for short) with multiple source places. The E-nets involved are pairwise disjoint, i.e., their underlying Petri nets are disjoint. When combining them into an I-net, output and input transitions are matched via their message types. Definition 2. Let n ≥ 2. Let V = {Ei | i ∈ [n]} be a set of pairwise disjoint E-nets with Ei = (Pi, [Ti,int, Ti,inp, Ti,out], Fi, Mi) for each i ∈ [n]. A matching over V is a bijection ϕ : Si∈[n] Ti,out → Sj∈[n] Tj,inp such that whenever t ∈ Ti,out and ϕ(t) ∈ Tj,inp, for some i, j, then i 6= j and Mi(t) = Mj (ϕ(t)). tu A set V of mutually disjoint E-nets is said to be composable if there exists a matching over V . To construct an I-net from a composable set V and a matching ϕ over V , matching output and input transitions of the E-nets in V are connected through (new) channel places using channel arcs. Definition 3. Let n ≥ 2. Let V = {Ei : i ∈ [n]} be a composable set of E-nets with Ei = (Pi, [Ti,int, Ti,inp, Ti,out], Fi, Mi) and Ti = Ti,int ∪ Ti,inp ∪ Ti,out for all i ∈ [n]. Let ϕ be a matching over V .
Then P (V, ϕ) = {[t, ϕ(t)] | t ∈ Ti,out, i ∈ [n]} is the set of channel places of V and ϕ, and F (V, ϕ) = {(t, [t, ϕ(t)]) | t ∈ Ti,out, i ∈ [n]}∪{([t, ϕ(t)], ϕ(t)) | t ∈ Ti,out, i ∈ [n]} is the set of channel arcs of V and ϕ. The sets P (V, ϕ), F (V, ϕ), and Pi, Ti, Fi, where i ∈ [n], are all pairwise disjoint. The Industry net over (V, ϕ) is the Petri net I(V, ϕ) = (P, T, F ) with P = Si∈[n] Pi ∪ P (V, ϕ), T = Si∈[n] Ti, and F = Si∈[n] Fi ∪ F (V, ϕ). tu
The notion of an E-net can be considered a generalisation of the notion
of a workflow net through its underlying net. This generalisation is
motivated, in particular, by the observation that workflows in enterprises often
interact with workflows in other enterprises by a bilateral, asynchronous
exchange of messages of a specified type (see eg., [
Example 1. Consider two enterprises, an Investment Firm (IF) and an Exchange (EX), modelled by the E-nets EIF and EEX in Figs. 1a and 1b, respectively. The Investment Firm sends order messages to the Exchange (modelled by output transition so with message type mo). The Exchange, upon receiving a message (via input transition ro with message type mo), subsequently sends an order confirmation message to the Investment Firm (output transition sc with message type mc). Then I(V, ϕ), the I-net in Fig.1c, with V = {EIF , EEX } and ϕ defined by ϕ(so) = ro and ϕ(sc) = rc, models the collaboration between the Investment Firm and the Exchange. Note that V allows only one matching. tu
The ideas underlying the concepts of E-nets and I-nets belong to a
wellestablished branch of research concerned with composing systems modelled
as Petri nets, into larger correctly functioning (concurrent) systems (see
eg., [
(c) The I-net Let V , ϕ, and I(V, ϕ) = (P, T, F ) as specified in Definition 3, be fixed for this section, and for Section 4 and Section 5.
Clearly, the construction of I(V, ϕ) does not affect the internal structure of the E-nets in V and the set of source places of I(V, ϕ) consists of all source places of the Ei. Moreover, removing channel places does not restrict the behaviour of an E-net. Consequently, all firing sequences in L(I(V, ϕ)) are combinations of firing sequences from the languages of the component nets. Lemma 1. If w ∈ L(I(V, ϕ)), then projTi (w) ∈ L(Ei) for all i ∈ [n]. tu On the other hand, the composition of E-nets into an I-net adds a channel place to the preset of each input transition. Consequently, the behaviour of an E-net may become restricted in the I-net. The property defined next describes how the occurrence of input transitions depends on the occurrence of output transitions.
Definition 4. Let w ∈ T ∗. Then w has the prefix property with respect to ϕ if #a(u) ≤ #ϕ−1(a)(u) for all prefixes u of w and all a ∈ Tinp. A language L ⊆ T ∗ has the prefix property with respect to ϕ if all w ∈ L have this property.
We will omit the reference to ϕ as it is fixed.
The asynchronous communication between its component E-nets guarantees that the firing sequences of I(V, ϕ) have the prefix property. Lemma 2. If w ∈ L(I(V, ϕ)), then w has the prefix property. tu tu Conversely, any sequence w ∈ T ∗ that can be (locally) executed by all E-nets and that satisfies the prefix property, belongs to L(I(V, ϕ)). Lemma 3. Let w ∈ T ∗ be such that projTi (w) ∈ L(Ei) for all i ∈ [n]. If w has the prefix property, then w ∈ L(I(V, ϕ)). tu Example 2. (Ex. 1 ctd.) Let T = {so, rc, ro, sc}. Let w = hso, ro, sc, rci.2 Now projTIF (w) = hso, rci ∈ L(EIF ) and projTEX (w) = hro, sci ∈ L(EEX ), where TIF and TEX are the sets of transitions of EIF and EEX , respectively. Obviously, w has the prefix property. Thus w ∈ L(I(V, ϕ)) by Lemma 3. For w0 = hso, ro, rc, sci, the prefix property does not hold: in u = hso, ro, rci, a prefix of w0, we have #rc(u) = 1, but #sc(u) = 0. Indeed, w0 6∈ L(I(V, ϕ)) although projTIF (w0) = projTIF (w) and projTEX (w0) = projTEX (w). tu Combining the above three lemmas yields Theorem 1. Let L ⊆ T ∗. Then L ⊆ L(I(V, ϕ)) if and only if L has the prefix property and projTi (L) ⊆ L(Ei) for all i ∈ [n]. tu From Lemma 1 and Theorem 1, it follows that whenever there exists a language L with the prefix property and for which projTi (L) = L(Ei) for all i ∈ [n], the I-net captures the full unrestricted behaviour of each E-net. Corollary 1. Let L ⊆ T ∗ be such that L has the prefix property and projTi (L) = L(Ei) for all i ∈ [n]. Then projTi (L(I(V, ϕ))) = L(Ei) for all i ∈ [n]. tu It should however be noted, that the conditions on L in Corollary 1 do not imply that L(I(V, ϕ)) = L. By Theorem 1, L ⊆ L(I(V, ϕ)) and as we argue next, this inclusion may be strict. 4
Whereas the prefix property is based on a simple comparison of numbers of occurrences, assignment functions, as defined next, relate each occurrence of an input transition to a corresponding occurrence of an output transition. Definition 5. An assignment function with respect to ϕ for a word w ∈ T ∗ is an injective function θ : (occ(w) ∩ (Tinp × N)) → occ(w) such that for every occurrence (b, j) ∈ occ(w) with b ∈ Tinp, θ(b, j) = (a, i) where a = ϕ−1(b) and i is such that posw(a, i) < posw(b, j). tu 2 The elements of the alphabet T are symbols consisting of two letters. In order to avoid confusion, we denote in this and similar examples, any sequence a1 · · · an with ai ∈ T for each i ∈ [n] by ha1, · · · , ani. Again, since ϕ is fixed, we will omit the reference to ϕ.
Remark 1. Clearly, every word for which an assignment function exists, has the prefix property. Conversely, whenever a word has the prefix property it has at least one (in general, more than one) assignment function. Example 3. Assume T = {a, b} and ϕ(a) = b. Let w = aabb. Then w has two assignment functions: θ defined by θ(b, 1) = (a, 1) and θ(b, 2) = (a, 2); and θ0 defined by θ0(b, 1) = (a, 2) and θ0(b, 2) = (a, 1). tu tu tu Each assignment function for w determines a partial order on occ(w). Definition 6. Let w ∈ T ∗ and let θ be an assignment function for w. Let (a, i), (b, j) ∈ occ(w), with a ∈ Tk and b ∈ Tl for some k, l ∈ [n]. Then (a, i) ≤w,θ (b, j) if (1) k = l and posw(a, i) ≤ posw(b, j) or (2) k 6= l and b ∈ Tinp and θ(b, j) = (a, i). tu By condition (1), ≤w,θ incorporates the ordering of occurrences of transitions in w that originate from the same E-net; by (2), it reflects the order of occurrences of input transitions and their assigned occurrences of output transitions.
Lemma 4. Let w ∈ T ∗ and let θ be an assignment function for w. Then ≤w+,θ, the transitive closure of ≤w,θ, is a partial order on occ(w). tu The linearisations of ≤w+,θ, where w is a word and θ an assignment function for w, define a set of words that can be obtained from w by (repeatedly) interchanging the positions of unrelated occurrences.
Definition 7. Let w ∈ T ∗ and let θ be an assignment function for w. Then linθ(w) = {v ∈ T ∗ | occ(v) = occ(w) and for all x, y ∈ occ(v), x ≤w+,θ y implies posv(x) ≤ posv(y)} is the set of θ-linearisations of w. tu Clearly w ∈ linθ(w) whenever linθ(w) is defined.
Remark 2. Let w and θ as in Definition 7 and let v ∈ linθ(w). Then (1) projTi (v) = projTi (w) for all i ∈ [n] and (2) θ is an assignment function for v and linθ(v) = linθ(w). From (2) and Remark 1, it follows that v has the prefix property. Example 4. (Ex. 3 ctd.) Let v = abab. Then occ(v) = occ(w) and linθ(w) = {v, w}. Clearly, θ is an assignment function for v and linθ(v) = linθ(w). Note that linθ0 (w) = {w} and θ0 is not an assignment function for v. tu By combining Remark 2 with Lemma 3, the statement of Lemma 3 can be strengthened. This shows that whenever a word with the prefix property can be locally executed by all component E-nets, then, for all its assignment functions θ, each of its θ-linearisations can be executed globally by the I-net. Theorem 2. Let w ∈ T ∗ be such that projTi (w) ∈ L(Ei) for all i ∈ [n]. If θ is an assignment function for w, then linθ(w) ⊆ L(I(V, ϕ)). tu Example 5. The I-net in Fig. 2 is an extension of the I-net from Example 2. The Exchange, after sending a confirmation (output transition sc) to the Investment Firm, can send (output transition si) a settlement instruction to the Central Securities Depositary (CD) to transfer ordered securities to the Investment Firm. The Central Securities Depositary - after receiving (input transition ri matching si) the settlement instruction - sends (output transition ss) a confirmation of settlement to the Investment Firm (that receives the message via input transition rs). Let w = hso, ro, sc, rc, si, ri, ss, rsi. So, w can be (locally) executed by each of the three enterprise nets in Fig. 2. Also, w has the prefix property (w.r.t. ϕ displayed in Fig. 2). Hence w is in the language of the I-net in Fig. 2. Define θ by θ(ro, 1) = (so, 1), θ(rc, 1) = (sc, 1), θ(ri, 1) = (si, 1), and θ(rs, 1) = (ss, 1). This θ is an (the only) assignment function for w (w.r.t. ϕ). Consider v = hso, ro, sc, si, rc, ri, ss, rsi, obtained from w by exchanging (si, 1) and (rc, 1). These occurrences are not ordered by ≤w+,θ. Hence v ∈ linθ(w) and v is, like w, in the language of the I-net. tu
By Theorem 2, every assignment function θ for a word w with the prefix property determines a set of words linθ(w) that can be executed by the I-net, provided w can be locally executed by all component E-nets. As remarked earlier, a word with the prefix property may have more than one assignment function. In this section we demonstrate that considering one particular type of assignment function is sufficient to describe all possible linearisations. Intuitively, in terms of the I-net, one could say that each assignment function describes for each occurrence of an input transition, which token it should take from its input channel place (namely the token deposited by the assigned occurrence of its output transition). Based on this point of view, the following two types of assignment functions represent natural policies to deal with the messages (tokens) in the channel places. Definition 8. Let w ∈ T ∗ and let θ be an assignment function for w. Then (1) θ is of type FIFO with respect to ϕ if, θ(b, j) = (ϕ−1(b), j) for every (b, j) ∈ occ(w) such that b ∈ Tinp; (2) θ is of type Stack with respect to ϕ if, for every (b, j) ∈ occ(w) such that b ∈ Tinp, θ(b, j) = (a, i) where a = ϕ−1(b), w = xaybz, for some x, y, z ∈ occ(w) such that #b(y) = #a(y), and j = #b(xayb) and i = #a(xa). tu Again, since ϕ is fixed, we will omit the reference to ϕ.
Every word with the prefix property has one assignment function of type FIFO and one of type Stack (and these functions may be the same). Example 6. (Ex. 3 and Ex. 4 ctd.) For w, the assignment function θ is of type FIFO and θ0 is of type Stack. Moreover, θ is an assignment function for v of type FIFO and of type Stack. tu In the sequel, θfifo denotes the assignment function of type FIFO of any w word w ∈ T ∗ with the prefix property. In addition, if L ⊆ T ∗ is a language that has the prefix property, then linFIFO(L) = S{linθwfifo (w) | w ∈ L} consists of all FIFO-linearisations of L.
Lemma 5. Let v, w ∈ T ∗ be such that v and w have the prefix property and occ(v) = occ(w). Then θvfifo = θwfifo. tu This observation does not hold for all assignment functions as can be seen in Example 6. Assignment functions of type FIFO are also special as they impose the least restrictive ordering (with for each occurrence of an input transition, only one occurrence of an output transition that precedes it). and thus a maximal (w.r.t. set inclusion) set of linearisations. Lemma 6. Let w ∈ T ∗ have the prefix property. Then linθwfifo (w) = {v ∈ T ∗ | v has the prefix property and projTi (v) = projTi (w) for all i ∈ [n]}. tu The inclusion from left to right is true for all assignment functions by Remark 2. The converse follows from Lemma 5 and Definition 7. Example 7. Let I(V, ϕ) be the I-net in Fig. 3 (extending Fig.1c). The Investment Firm from Example 2 can now send multiple orders to the Exchange. This is modelled using internal transitions in the E-nets: ii1 and ii2 for the Investment Firm and ei1 and ei2 for the Exchange. Let v = hei1, ii1, so, ii2, ro, ei2, so, ii2, ro, ei2, so, ro, sc, rci and let w = hei1, ii1, so, ii2, so, ii2, so, ro, ei2, ro, ei2, ro, sc, rci. Clearly, both v and w have the prefix property and projTi (v) = projTi (w) for i ∈ {1, 2} with T1 = {ii1, ii2, so, rc} and T2 = {ei1, ei2, ro, sc}. Let θ be the assignment function for w of type FIFO. Hence, by Lemma 6, v ∈ linθ(w). However, for the assignment function θ0 of w of type Stack (and thus θ0(ro, 1) = (so,3)), v ∈ linθ0 (w) does not hold. tu For a language L ⊆ T ∗ that has the prefix property, we denote by lin(L) the language consisting of all words that can be obtained as a θ-linearisation of any word w ∈ L in for whatever assignment function θ for w. Thus, lin(L) = S{linθ(w) | w ∈ L and θ an assignment function for w}.
Using Lemma 6, we obtain the following extension of Theorem 2. Theorem 3. Let L ⊆ T ∗ be a language with the prefix property such that projTi (L) ⊆ L(Ei) for all i ∈ [n].
Then L ⊆ lin(L) ⊆ linFIFO(L) ⊆ L(I(V, ϕ)). tu This theorem together with Theorem 1 shows that the languages of I-nets are closed under exchanging independent occurrences of transitions. Corollary 2. lin(L(I(V, ϕ))) = linFIFO(L(I(V, ϕ))) = L(I(V, ϕ)). tu 6
We are now ready to address our initial question: given an event log
(language), representing the observed behaviour of a given number of distinct,
collaborating enterprises, construct an I-net that generates this observed
behaviour. In this section, we will demonstrate how we can leverage
existing algorithms for the discovery of isolated (local) processes, to solve this
problem. A formal definition of such a process discovery algorithm, based
on [
Definition 9. Let L be a family of languages. A process discovery algorithm A for L is an algorithm that computes for all L ∈ L, a Petri net A(L) = (P, T, F ) with a single source place and such that T = Alph(L) and L ⊆ L(A(L)). tu To leverage such algorithms to a system of asynchronously communicating nets, one needs to describe the distribution of actions over components in combination with their role as internal, input, or output action. This leads to the concept of a distributed communicating alphabet defined next. Definition 10. Let n ≥ 1. An n-dimensional distributed communicating alphabet (or n-DCA, for short) is a tuple DA = ([Σ1, . . . , Σn], [Σint, Σinp, Σout], mt, cp) such that – Σ1, . . . , Σn are non-empty, pairwise disjoint alphabets; – Σint, Σinp, Σout are pairwise disjoint alphabets consisting of internal actions, input actions and output actions, respectively; – Si∈[n] Σi = Σint ] Σinp ] Σout; – mt : Σinp ∪ Σout → M is a function that assigns message types to the input and output actions; – cp : Σinp ∪ Σout → Σinp ∪ Σout is a ( complementing) bijection, which is not defined (cp = ∅) if n = 1, and otherwise (n ≥ 2), for all a ∈ Σinp ∪Σout: if a ∈ Σinp, then cp(a) ∈ Σout and if a ∈ Σout, then cp(a) ∈ Σinp; if a ∈ Σi for some i ∈ [n], then cp(a) ∈ Σj where j ∈ [n] is such that i 6= j; mt(cp(a)) = mt(a); and cp(cp(a)) = a. tu The alphabet Si∈[n] Σi = Σint ] Σinp ] Σout in Definition 10, also referred to as the underlying alphabet of the n-DCA DA, is intended to represent the actions available to n interacting enterprises. DA describes both their distribution across the enterprises and their interaction capacities. A 1-DCA consists of a single enterprise. When specifying a 1-DCA, we can omit its complementing bijection cp as it is not defined (and not needed). For i ∈ [n], we refer to the 1-DCA DAi = ([Σi], [Σi,int, Σi,inp, Σi,out], mti) as the i-th component of DA.
For the rest of this section we assume a fixed family of languages L and a fixed process discovery algorithm A for L. The following definition describes how A can be used to discover E-nets.
Definition 11. The E-net discovery algorithm derived from A, is the algorithm AE that computes, for all pairs (L, DA) such that L ∈ L with A(L) = (P, T, F ), and DA = ([T ], [Tint, Tinp, Tout], mt) is a 1-DCA with Alph(L) = T as its underlying alphabet, the E-net AE(L, DA) = (P, [Tint, Tinp, Tout], F, mt). tu Thus AE adds the information from DA to the transitions of A(L). Clearly, AE(L, DA) is an E-net. 3 From Definitions 9 and 11, we have L ⊆ L(A(L)) = L(E). Now we move to the discovery of I-nets on basis of A. Definition 12. The I-net discovery algorithm derived from A, is the algorithm AI that computes, for all pairs (L, DA) such that – DA = ([Σ1, . . . , Σn], [Σint, Σinp, Σout], mt, cp) is an n-DCAfor an n ≥ 2, – Alph(L) = Si∈[n] Σi, the underlying alphabet of DA, and – projΣi (L) ∈ L for all i ∈ [n], the I-net AI (L, DA) = I(V, ϕ) with V = {AE(projΣi (L), DAi) | i ∈ [n]} and ϕ(a) = cp(a) for all a ∈ Σout. tu Note that AI (L, DA) = I(V, ϕ) in Definition 12 is indeed an I-net, since, by Definition 11, for all i ∈ [n], AE(projΣi (L), DAi) is an E-net with set of transitions Σi; the Σi are mutually disjoint; and the properties of cp described in Definition 10 guarantee that ϕ is a matching for V .
By Definitions 9 and 12, we can transfer Theorem 1, Corollary 1, and
Theorem 3 to the setting of discovering an I-net from a given language L.
Theorem 4. Let L be a language with the prefix property. Let n ≥ 2 and
let DA be an n-DCA with Alph(L) as its underlying alphabet
Let AI (L, DA) = I(V, ϕ) with V = {Ei | i ∈ [n]}. Then
(1) L ⊆ lin(L) ⊆ linFIFO(L) ⊆ L(I(V, ϕ));
(2) projΣi (L(I(V, ϕ))) = projΣi (L) if projΣi (L) = L(Ei) for all i ∈ [n],
where for each i ∈ [n], Σi is the underlying alphabet of DAi. tu
3 In case A is an algorithm for the discovery of workflow nets, like the Inductive
Miner [
Example 8. (Ex. 7 ctd.) Let w and v be as in Example 7 and let L = {w}. Let DA = ([ΣIF , ΣEX ], [Σint, Σinp, Σout], mt, cp) be the 2-DCA, with components DAIF and DAEX , as given in Fig. 4, representing the actions available to the collaboration between the Investment firm and the Exchange from Example 7. Let AE and AI be the E-net and I-net discovery algo
Fig. 4: The 2-DCA DA rithms respectively, derived from a process discovery algorithm A. Furthermore, AE(projΣIF (L), DAIF ) = EIF and AE(projΣEX (L), DAEX ) = EEX are as depicted in Figs. 5.(a) and (b) respectively. Then AI (L, DA) = I(V, ϕ) is the I-net in Fig. 3. Since L satisfies the “if” conditions in Theorem 1, L ⊆ L(I(V, ϕ)). Moreover, as v ∈ linFIFO(w) we have from Theorem 4, that also v ∈ L(I(V, ϕ)) tu 7
In this paper we have considered the problem of discovering a distributed
process model (in the form of an I-net) from an event log (given in the form
of a language). Moreover, the number of participating processes (modelled
as E-nets) is given together with their channels (in the form of matching
input and output actions). We have shown how an (existing) algorithm
for the discovery of Petri net models from event logs of individual
processes could be used in a new, distributed, algorithm to discover an I-net.
Moreover, by Theorem 1, fitness of the I-net produced by the algorithm is
guaranteed if and only if fitness of the component nets is guaranteed and
the event log has the prefix property (a natural assumption for event logs
of distributed processes composed of components that interact via
asynchronous communication channels). It is interesting to reflect on the
inclusion of these linearisations (see Corollary 2 and Theorem 4.(1)) and the
role of the channels. The exchange of independent occurrences of actions
suggests a relationship to the well-known Mazurkiewicz traces (equivalence
classes of words, see, eg., [
Returning to the discovering of distributed process models, it was our
initial idea to investigate to what extent existing algorithms for the
discovery of single (isolated) processes could be used to discover distributed
systems. The subject of process mining is an active research area, that has
resulted in many process discovery algorithms (see, eg., [