Industry nets have been introduced in [18] as a framework to model global communication between enterprises where the design of their internal operations is left to the local level. In this set-up, operations at the enterprise level are represented by Enterprise nets (Petri nets with input, output, and internal transitions) and Industry nets are compositions of Enterprise nets that interact by exchanging messages through channels. In [18], a method is proposed to establish global compliance of an Industry net with a reference model by local checks (of Enterprise nets) only. In this paper, we focus on the discovery of Industry nets from a description of the (observed) global behaviour of a collection of collaborating enterprises.
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., [6,8,11]). Here, we take advantage of this and consider the discovery of distributed processes (modelled as Industry nets) assuming the existence of an algorithm for the discovery of component processes (in the form of Enterprise nets with their own activities). To be precise, we first demonstrate how an algorithm that computes from an event log a Petri net, say a workflow net [7] (the Inductive Miner [19] is an example of such an algorithm), can be adapted to yield an Enterprise net. Then, given some global behaviour and the local event logs determined by it, an Industry net is constructed by combining the Enterprise nets discovered from the respective local event logs.
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.
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 R ⊆ A × A such that R ⊆ R , 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 = a 1 • • • a n , with n ≥ 0 and a i ∈ Σ, 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
In addition, we allocate a position with each occurrence of w through the function pos w : occ(w) → [|w|] as follows: for all (a, i) ∈ occ(w), pos w ((a, i)
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 = (P , T , F ) is a Petri net such that P ∪T and P ∪T have no elements in common, then N and N 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 µ of N , denoted
We extend the notation µ − → N µ for some marking µ } 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 [7]) is a Petri net with exactly one source and one sink place such that every place and every transition are on a path from source to sink.
Enterprise nets and Industry nets We recall the definitions of Enterprise and Industry nets from [18]. Enterprise nets (or E-nets, for short) are Petri nets equipped for asynchronous communication with other E-nets; they have transitions for inputting and transitions for outputting. An interaction between E-nets is realised by an occurrence of an output transition of one E-net and a (later) occurrence of an input transition of another E-net with a matching message type. We let M denote the set of message types fixed throughout this paper. Definition 1. An Enterprise net is a tuple E = (P, [T int , T inp , T out ], F, M ) such that T int , T inp , and T out are mutually disjoint sets; T int is the set of internal transitions of E, T inp its set of input transitions, and T out its set of output transitions; furthermore, the underlying Petri net of E, und(E) = (P, T int T inp T out , F ), is a Petri net with exactly one source place; finally M : T inp ∪ T out → M is the communication function of E.
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.
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.
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., [20,16,24,12]). The similarity between E-nets and workflow nets, moreover, allows us to leverage the large amount of research into the automated discovery of workflow nets, for the purpose of automated discovery of E-nets. The term "Industry", in "Industry net", is used loosely to refer to any group of collaborating enterprises.
Example 1. Consider two enterprises, an Investment Firm (IF) and an Exchange (EX), modelled by the E-nets E IF and E EX in Figs. 1a and 1b, respectively. The Investment Firm sends order messages to the Exchange (modelled by output transition so with message type m o ). The Exchange, upon receiving a message (via input transition ro with message type m o ), subsequently sends an order confirmation message to the Investment Firm (output transition sc with message type m c ). Then I(V, ϕ), the I-net in Fig. 1c, with V = {E IF , E EX } 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.
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., [13,14,22,23]). In [1] and also in [25] compositions of so-called open workflow nets are considered. These are Petri nets with interface places to communicate with other Petri nets. In [14], similar to the set-up of I-nets, local Petri nets do not have interface places but they communicate via distinguished input and output labels. As mentioned in [14], the advantage of this approach is that it leads to a better separation of concerns: eg., the designer of a local system does not have to consider how it will be used; this is a concern for the designer of the global system.
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 E i . 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.
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 ∈ T inp . 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. 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, ϕ)). From Lemma 1 and Theorem 1, it follows that whenever there exists a language L with the prefix property and for which proj Ti (L) = L(E i ) for all i ∈ [n], the I-net captures the full unrestricted behaviour of each E-net. 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.
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) ∩ (T inp × N)) → occ(w) such that for every occurrence (b, j) ∈ occ(w) with b ∈ T inp , θ(b, j) = (a, i) where a = ϕ −1 (b) and i is such that pos w (a, i) < pos w (b, j).
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. 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).
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 pos v (x) ≤ pos v (y)} is the set of θ-linearisations of w.
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) proj Ti (v) = proj Ti (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 θ (w) = {w} and θ is not an assignment function for v.
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. Let w = so, ro, sc, rc, si, ri, ss, rs . 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 = so, ro, sc, si, rc, ri, ss, rs , 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.
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 ∈ T inp ;
(2) θ is of type Stack with respect to ϕ if, for every (b, j) ∈ occ(w) such that b ∈ T inp , θ(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).
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 θ is of type Stack. Moreover, θ is an assignment function for v of type FIFO and of type Stack.
In the sequel, θ fifo w denotes the assignment function of type FIFO of any word w ∈ T * with the prefix property. In addition, if L ⊆ T * is a language that has the prefix property, then lin FIFO (L) = {lin θ fifo w (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
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. 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. Fig. 3: I-net with option to repeat orders Let v = ei1, ii1, so, ii2, ro, ei2, so, ii2, ro, ei2, so, ro, sc, rc and let w = ei1, ii1, so, ii2, so, ii2, so, ro, ei2, ro, ei2, ro, sc, rc . Clearly, both v and w have the prefix property and proj Ti (v) = proj Ti (w) for i ∈ {1, 2} with T 1 = {ii1, ii2, so, rc} and T 2 = {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 θ of w of type Stack (and thus θ (ro, 1) = (so,3)), v ∈ lin θ (w) does not hold.
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) = {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
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, ϕ))) = lin FIFO (L(I(V, ϕ))) = L(I(V, ϕ)).
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 [6], is given next.
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)).
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
then cp(a) ∈ Σ j where j ∈ [n] is such that i = j; mt(cp(a)) = mt(a); and cp(cp(a)) = a.
The alphabet i∈[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 DA i = ([Σ i ], [Σ i,int , Σ i,inp , Σ i,out ], mt i ) 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 A E that computes, for all pairs (L, DA) such that L ∈ L with A(L) = (P, T, F ), and DA = ([T ], [T int , T inp , T out ], mt) is a 1-DCA with Alph(L) = T as its underlying alphabet, the E-net A E (L, DA) = (P, [T int , T inp , T out ], F, mt).
Thus A E adds the information from DA to the transitions of A(L). Clearly, A E (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. Note that A I (L, DA) = I(V, ϕ) in Definition 12 is indeed an I-net, since, by Definition 11, for all i ∈ [n], A E (proj Σi (L), DA i ) 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
where for each i ∈ [n], Σ i is the underlying alphabet of DA i . Thus, given a language L with the prefix property representing an event log of a system of n enterprises, and an n-dimensional distributed communicating alphabet, we can construct an I-net as described in Definition 12. This I-net has all words in L as firing sequences together with all their linearisations (obtained by exchanging occurrences of independent actions). In fact, it is sufficient to consider only their FIFO-linearisations. Even then, though, there may be more firing sequences than what can be deduced from the description L of the observed behaviour. By Theorem 4.( 2), a precise fit of the enterprise nets is preserved in the I-net constructed. We are currently working on a characterisation of properties of L that would guarantee that the language of L is exactly lin(L).
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 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., [21]) and their dependence graphs (defining their causal structure in the form of a labelled partial order, see [15]). There is however an important difference: independence in Mazurkiewicz' theory is between actions rather than their occurrences. The independence between occurrences considered here can be seen as being context sensitive and determined by the history leading to these occurrences which leads to a theory of context dependent or local traces (see, eg., [10,17]). In [14], a model similar to our I-nets is considered. There channel properties are investigated in terms of asynchronous I/O-transition systems rather than languages. The asynchronously composed I/O-Petri nets considered, use communication channels modelled by places of Petri nets rather than imposing the usual FIFO requirement of communication channels. However, as can be seen from our results, choosing FIFO channels or the standard unordered places, does not affect the language.
Returning to the discovering of distributed process models, it was our initial idea to investigate to what extent existing algorithms for the dis-covery 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., [6] for an overview). Typically, these algorithms allow for the discovery of local processes in isolation, i.e., interaction between processes is not taken into account. Note that the approach as outlined here, is also different from the one followed in [2,4] where the problem of process mining from large event logs is addressed. There, different options to distribute the mining problem over sublogs (with overlapping activities) are considered, whereas in the current paper we assume the (disjoint) components given. Of special interest are the passages from [3]. Provided a causal structure (a 'skeleton' of the process) is known, a larger model can be decomposed into (synchronising) fragments making a divide-and-conquer approach possible In [9] the event logs of Multi Agent Systems are projected onto each agent to discover component models in terms of workflow nets by using existing process discovery algorithms, similar to our approach. By means of α-morphisms an abstraction of each component model is derived. The aim of [9] however, is to show that if the composition of these abstract models is sound, the composition of the original component models is sound.