The problem of synthesis of Petri nets from transition systems or languages has many applications, ranging from CAD for VLSI to medical applications, among others. The most common algorithms to accomplish this task are based on the theory of regions. However, one of the problems of such algorithms is its space requirements: for real-life or industrial instances, some of the region-based algorithms cannot handle in memory the internal representation of the input or the exploration lattice required. In this paper, the incremental derivation of a basis of regions and the later partitioned basis exploration is presented, which allows the splitting of large inputs.
The introduction of the theory of regions [1] in the early nineties enabled a new area of research that strives for transforming language or state-based representations into event-based ones. This transformation, known as synthesis, was initially devoted to derive a Petri net whose reachability graph was bisimilar or isomorphic to the input transition system. A variant of this problem, known as mining, has weaker requirements: the language of the derived Petri net must be a superset (maybe proper) of the language of the input transition system [2]. The theory of this paper provides algorithms for mining.
Many research has been carried out since the introduction of regions, specially of theoretical nature, which has brought a better understanding of the theory [3][4][5][6], and has provided meaningful extensions to make it more general [7][8][9][10].
As a consequence of the aforementioned theoretical work, tools based on the theory of regions started to be available by the end of the nineties [11,12] and still new ones are developed nowadays [9,10]. These tools are the outcome of bridging the gap between the theory and practice, and many of them are used extensively in the academic domain, whereas few are used in industry. The reasons for the limited success of these tools in industry might be:
1. The algorithms involved are complex, i.e. in general polynomial with the size of the input [3], that might be prohibitive for large inputs, and the use of efficient data structures like BDDs or heuristics only alleviates the problem. 2. No high-level techniques are provided to cope with the inherent complexity of the problem.
Basis B1
Basis B2 . . .
Sect. 3
Basis i Bi PN N
In [15] RG(Nn)
In [6,14] Sect. 4 In this work we provide the theoretical basis for deriving high-level strategies that may allow to handle large specifications. More concretely, as space requirements are typically the bottleneck for some of the tools listed above, in this paper we present an incremental technique that allows splitting the input into several smaller parts. Moreover, we show how the theory of regions can be extended algorithmically to combine the regions of each part in order to derive the regions of the whole input.
The theory presented will be oriented for the problem of mining: given a set of objects describing behaviors (like a Petri net, a transition systems or an event log) O 1 , O 2 , . . . , O n , we want to obtain a Petri net N such that L(N ) ⊇ n i=1 L(O i ). The traditional way to solve this problem is to generate a transition system A i for each O i , join all these A i to create a single transition system, and then apply a synthesis technique to derive a Petri net from a transition system [12,13].
In this paper we explore a different approach. Instead of working with a monolithic transition system, we use the fact that a transition system can be represented by a basis of regions, such that any other region is a linear combination of the regions in the basis (a recent publication shows an efficient technique to accomplish this task [14]). Then, bases can be combined to obtain a region basis for the whole system, from which we can derive the Petri net N .
The general picture of the approach of this paper is outlined on Fig. 1(a). Some arcs are labeled with an indication of the section or the reference where the conversion/operation is explained. Basically the first step is to convert inputs that are not transition systems into a transition system, and then compute a region basis from which a PN can be generated. Another possible application is also shown in Fig. 1(b), where a large TS is split into smaller subsystems of manageable size, with the only restriction that all the subsystems must include the initial state and be connected.
In [16] an incremental approach was suggested based on the observation that any region of the union of two transition systems can be expressed as the union of regions of those systems. As in the approach presented in this paper, the approach in [16] trades space for time, since it must first compute all the regions and then obtain the minimal ones, a slower process than finding directly the minimal regions if the whole transition system fits into memory. The main drawback of this method is that the complete set of regions of each component transition system must be stored (either in memory or disk) in order to compute the set of regions of the union. In this work we propose a faster methodology based on the fact that the complete set of regions can be succintly represented by a basis of regions.
We start by giving the necessary background in Sect. 2. The process of combining a set of bases to produce a unique basis for the whole system is explained in Sect. 3. A description of the generation of a PN from a region basis is given in Sect. 4 and, finally, Sect. 5 concludes this paper.
Definition 1 (Transition system). A transition system (TS) is a tuple S, Σ, T, s 0 , where S is a set of states, Σ is an alphabet of actions, T ⊆ S × Σ × S is a set of (labelled) transitions, and s 0 ∈ S is the initial state.
We use s e −→s as a shortcut for (s, e, s ) ∈ T , and we denote its transitive closure as * −→. A state s is said to be reachable from state s if s * −→s . We extend the notation to transition sequences, i.e., s 1 σ −→s n+1 if σ = e 1 . . . e n and (s i , e i , s i+1 ) ∈ T . We denote #(σ, e) the number of times that event e occurs in σ. Let A = S, Σ, T, s 0 be a TS. We consider connected TSs that satisfy the following axioms: i) S and Σ are finite sets, ii) every event has an occurrence and iii) every state is reachable from the initial state. The language of a TS A, L(A), is the set of transition sequences feasible from the initial state.
For two TSs A 1 and A 2 , when L(A 1 ) ⊆ L(A 2 ), we will say that A 2 is an over-approximation of A 1 .
Clearly, the TS A 1 ∪ A 2 is an over-approximation of the TSs A 1 and A 2 , i.e.
Definition 3 (Petri net [17]). A Petri net (PN) is a tuple (P, T, W, M 0 ) where the sets P and T represent disjoint finite sets of places and transitions, respectively, and W : (P × T ) ∪ (T × P ) → N is the weighted flow relation. The initial marking M 0 ∈ N P defines the initial state of the system.
Firing an enabled transition t in a marking M leads to the marking M defined by M (p) = M (p) − W (p, t) + W (t, p), for p ∈ P , and is denoted by M t → M . The set of all markings reachable from the initial marking M 0 is called its Reachability Set. The Reachability Graph of N , denoted RG(N ), is a transition system in which the set of states is the Reachability Set, the events are the transitions of the net and a transition (M 1 , t, M 2 ) exists if and only if M 1 t → M 2 . We use L(N ) as a shortcut for L(RG(N )).
The theory of regions [1,5] provides a way to derive a Petri net from a transition system. Intuitively, a region corresponds to a place in the derived Petri net. In the initial definition, a region was defined as a subset of states of the transition system satisfying a homogeneous relation with respect to the set of events. Later extensions [7,18,10] generalize this definition to multisets, which is the notion used in this paper. Definition 4 (Multiset, k-bounded Multiset, Subset). Given a set S, a multiset r of S is a mapping r : S → Z. The number r(s) is called the multiplicity of s in r. Multiset r is k-bounded if all its multiplicities are less or equal than k. Multiset r 1 is a subset of r 2 (r 1 ⊆ r 2 ) if ∀s ∈ S : r 1 (s) ≤ r 2 (s).
We define the following operations on multisets: Definition 5 (Multiset operations).
The operations described above have algebraic properties, e.g., r + r = 2 • r and
Definition 6 (Gradient). Let S, Σ, T, s 0 be a TS. Given a multiset r and a transition s e −→s ∈ T , its gradient is defined as δ r (s e −→s ) = r(s ) − r(s). If all the transitions of an event e ∈ Σ have the same gradient, we say that the event e has constant gradient, whose value is denoted as δ r (e). We say that region r is normalized if minp(r) = 0. Similarly, it is nonnegative if minp(r) ≥ 0. Any region r can become normalized by subtracting minp(r) from the multiplicity of all the states. Definition 8 (Normalization). We denote by ↓r the normalization of a region r, so that ↓r = r − minp(r).
It is useful to define a normalized version of the sum operation between regions, since it is closed in the class of normalized regions. Definition 9 (Normalized sum). Let r 1 and r 2 be normalized regions, we denote by r 1 ⊕ r 2 their normalized sum, so that r 1 ⊕ r 2 =↓(r 1 + r 2 ). Definition 10 (Gradient vector). Let r be a region of a TS whose set of events is Σ = {e 1 , e 2 , . . . , e n }. The gradient vector of r, denoted as ∆(r), is the vector of the event gradients, i.e. ∆(r) = (δ r (e 1 ), δ r (e 2 ), . . . , δ r (e n )). Proposition 1. Gradient vectors have the following properties: Regions can be partitioned into classes using their gradient vectors.
Definition 11 (Canonical region). Two regions r 1 and r 2 are said to be equivalent if their gradient is the same, i.e. r 1 ≡ r 2 ⇔ ∆(r 1 ) = ∆(r 2 ). Given a region r, the equivalence class of r, is defined as [r] = {r i | r i ≡ r}. A canonical region is the normalized region of an equivalence class, i.e. ↓r.
Example of canonical regions are provided in Fig. 4, where two TSs are shown in which some regions have been shadowed. For instance, the canonical region r 0 = {s 1 , s 2 } has gradient vector ∆(r 0 ) = (1, 0). A PN built from the set of minimal canonical regions has the same language as a PN built using all the regions [5], thus it yields the smallest overapproximation with respect to the language of the TS [10].
Definition 12 (Subregion, Empty region, Minimal canonical region). r 1 is a subregion of r 2 , denoted as r 1 r 2 , if, for any state s, ↓r 1 (s) ≤ ↓r 2 (s). We denote by ∅ the region in which all states have zero multiplicity. A minimal canonical region r satisfies that for any other region r , if r r then r ≡ ∅.
In this section we detail how region bases of different TSs can be joined, yielding a region basis of their union. We will illustrate the theory with the running example shown in Fig. 3. In this case, we assume A is a very large TS that cannot be easily handled, hence it is split into two smaller subsystems, namely
Definition 13 (Region basis). Given a TS, a region basis B = {r 1 , r 2 , . . . , r n } is a minimal subset of the canonical regions of TS such that any region r can be expressed as a linear combination of B ( i.e. r = The set of canonical regions of a TS, together with the normalized sum operation, forms a free Abelian group [18]. Consequently, there exists a basis (i.e. subset of the group) such that every element in the group can be rewritten as a unique linear combination of the basis elements.
Region bases are interesting because, as the following theorem states, their size is usually small.
). Let S, Σ, T, s 0 be a TS. The size of the region basis is less or equal to min(|Σ|, |S| − 1).
Given two systems described by their region basis, we want to obtain the region basis of their union TS. The work more closely related is [16], in which it is described how the set of regions in the joined system can be obtained from the regions of the component systems. This is achieved by introducing the concept of compatible (standard) regions. In this section we first review and extend this concept of compatibility to generalized regions. Definition 14 (Compatible TSs). Two TSs A 1 and A 2 are compatible if they have the same initial state.
Def. 14 is more general than the one in [16], where the number of shared states is restricted to one (the initial state). For instance, systems A 1 and A 2 of Fig. 3 are compatible according to this definition, but not using the definition in [16], since they share states s 0 and s 2 .
Definition 15 (Compatible regions, offset). Two regions r 1 and r 2 from two compatible TSs A 1 = S 1 , Σ 1 , T 1 , s 0 and A 2 = S 2 , Σ 2 , T 2 , s 0 are said to be compatible if:
-∀e ∈ Σ 1 ∩Σ 2 , δ r1 (e) = δ r2 (e), i.e. they have the same gradient for all common events, and,
the difference in multiplicity of each shared state is equal to a constant, that we call the offset between r 1 and r 2 , denoted as off(r 1 , r 2 ).
Two compatible regions are said to be directly compatible if off(r 1 , r 2 ) = 0, a fact that we denote as r 1 ↔ r 2 . Conversely, if off(r 1 , r 2 ) = 0, we say that the regions are indirectly compatible and we use the following notation r 1 r 2 .
An immediate consequence of Def. 15 is that, if there is only a single shared state, then any two regions with the same gradient for all common events are compatible. This is, for instance, the case when TSs represent execution trees and only the initial state is shared among them.
Two compatible regions can be made directly compatible by adding the offset to one of them.
Definition 16 (Directly compatible region). Given two compatible regions r 1 and r 2 with off(r 1 , r 2 ) > 0, the directly compatible region of r 1 with respect to
Definition 17 (Union of compatible regions). Given two compatible regions r 1 and r 2 , defined over sets of states S 1 and S 2 , respectively, with off(r 1 , r 2 ) > 0, their union, denoted r 1 r 2 , is
Proposition 2 (Union of compatible regions is a region of union system). Given two compatible regions r 1 and r 2 of two compatible TSs A 1 and A 2 , r 1 r 2 is a region of A 1 ∪ A 2 . For each shared event, its gradient is equal to the gradient in r 1 or r 2 , which are equal. For non-shared events of A 1 (A 2 ), their gradient is the gradient in A 1 (A 2 ).
Proof. Assume off(r 1 , r 2 ) ≥ 0. Region r = r 1 r 2 , where r 1 ↑ r2 = r 1 + off(r 1 , r 2 ). The latter entails that, in a shared state s, the multiplicity is the same for r 1 ↑ r2 and r 2 , which is the multiplicity assigned to r. For non-shared states, on the other hand, the multiplicity assigned in r is the multiplicity of the region whose TS contains the state. Thus any arc (either going from a shared to nonshared state or any other combination) has a constant gradient, equal to the gradient of that event in the corresponding region. Result transfers to r 1 because ∆(r 1 ) = ∆(r 1 ↑ r2 ).
Example 2. In Fig. 5 we show one region of each subsystem of our running example. They are compatible, since the gradient of the single shared event a is the same in both regions. More specifically, they are indirectly compatible, since their offset is different than 0. Property 1. Given two compatible non-negative regions r 1 and r 2 . If they are directly compatible then r 1 r 2 is a normalized region, if and only if, one of them is normalized. If they are not directly compatible, but both of them are normalized, then again r 1 r 2 is a normalized region.
Proof. If one of them is normalized and they are directly compatible no modification of multiplicities is performed, so the state with 0 multiplicity will remain untouched and since regions are non-negative, then minp(r 1 r 2 ) = 0. Conversely, if r 1 r 2 is a normalized region and r 1 ↔ r 2 , then all multiplicities of either r 1 or r 2 are greater or equal to 0, and since there is at least one 0 multiplicity, at least one of them must be normalized. If both are normalized but are not directly compatible, only one of them modifies its multiplicities and we end up in the same situation.
Given two TSs, A 1 and A 2 . Let {r 1 , . . . , r n } be the region basis of A 1 and {q 1 , . . . , q m } the basis of A 2 . The set of all regions of the union system
) is obtained by finding all non-trivial solutions for x i variables that satisfy:
i.e. for all common events their gradient must be the same on both systems. This system of equations can be rewritten in matrix form as M •x = 0, where x is the column vector of variables x i and M is the following matrix: free variables, and then, for each free variable x i , derive a vector of the basis by assigning 1 to x i and 0 to the rest of free variables. The y i columns correspond to the combination of regions of both system that have the same gradient, and the resulting combined region is a region basis for the union TS.
Example 3. We will compute the region basis of the union of TSs A 1 and A 2 shown in Fig. 3. Two possible region basis for these systems are {r 0 , r 1 } and {q 0 , q 1 }, show in Fig. 4. The matrix M in this case is
where columns (from left to right) correspond to regions r 0 , r 1 , q 0 , q 1 and there is only a single row that corresponds to the only shared event between A 1 and A 2 , namely event a.
The set of shared states is {s 0 , s 2 }, thus the shared state conflict matrix C has only one row because only state s 2 is reachable from s 0 by firing a different multiset of events. Consequently C = r 0 (s 2 ) r 1 (s 2 ) −q 0 (s 2 ) −q 1 (s 2 ) . With matrices M and C we can now build
which is an indeterminate system with 2 degrees of freedom. We can write x 1 = 2x 2 + x 3 and x 0 = −x 2 − x 3 , so by changing the values of variables we can generate all the possible solutions. Given these parameters the region solution will be ((−
Using the parameter values (1, 0), and (0, 1) for vector (x 2 , x 3 ) we do obtain the following regions in the joined system: b 0 = (−r 0 + 2r 1 ) q 0 and b 1 = (−r 0 + r 1 ) q 1 . The set {b 0 , b 1 } forms a region basis for the A 1 ∪ A 2 system (see Fig. 6).
In [14] an algorithm was presented that allows finding minimal regions by careful exploration of the region space defined by the region basis. The fundamental idea is that the regions in the basis are initially assumed to be minimal, and then combinations of these regions can only yield a minimal region if the resulting region is non-normalized, since otherwise the region is a superregion of any of its component regions. However this approach cannot be directly used if the number of states in the monolithic TS is too high to easily perform region operations in memory. The alternative we propose in this paper is to partition the region operations into the different component TSs, so that each time only the information of one of the systems is accessed.
To achieve this partitioning, consider the region basis {b 0 , . . . , b n }, we denote by b j i the part of region b i that belongs to subsystem j. All the regions in the basis are assumed to be normalized, but the different b j i could be non-normalized, since they are defined so that, given i, all b j i are directly compatible (cf. Def. 15). For instance region b 0 in Fig. 6 At this point we must check for minimal regions. The list of candidates includes all the regions in the basis (and their coregions), that is all the combinations in the second level, as well as combinations (1, −1) and (−1, 1) that have been found during the exploration. To check for minimality, we create a partial order among all these combinations in each subsystem (see Fig. 8). A region is not minimal if there is a combination, different than (0, 0), that appears before it in all the partial orders. In our example, combinations (1, 0) and (−1, 0) are not minimal. Conversely, for instance (−1, 1) is minimal because, although combination (0, −1) precedes it in A 1 (i. ). With the minimal regions found we build the mined PN of Fig. 9. For a set of subsystems A 1 , . . . , A n the algorithm can be summarized as follows:
-Take the first subsystem (A 1 ) and explore region space until either combinations are exhausted (according to the user defined bounds on the coefficients) or the border of non-normalized regions is found. -Pass to next subsystem the set of combinations of non-normalized regions and check for normality in this other subsystem.
• If region is normalized, then discard, but mark sibling combinations to be explored in the current subsystem (since all sibling combinations in the first subsystem will remain to be non-normalized). • On the other hand, if region is non-normalized and we are not in the last subsystem, then add it to the list of regions that conform the border of non-normalized regions that will be passed to next subsystem. If we are already in the last subsystem, then add the combination to the list of candidate minimal regions, normalize it, and then check the normalization status in all subsystems. Sibling combinations are scheduled to be explored in the first subsystem whose subpart of the region is normalized.
In this paper we have extended the theory developed in [14] to devise an incremental algorithm for process mining. Given that space requirements are often the
where c is the number of common events in the system, i.e. c = |Σ 1 ∩ Σ 2 |. We call this matrix the gradient compatibility matrix between A 1 and A 2 .
Compatibility of regions demands not only the gradients of common events to be the same, but also that the offset is the same for all shared states. To enforce such condition, assume that we shift all the regions in the bases {r 1 , . . . , r n } and {q 1 , . . . , q m } so that for all r i and q j we have that r i (s 0 ) = q j (s 0 ) = 0. Now any region obtained by combining the regions in the bases will have a 0 multiplicity in the initial state. Thus, if the offset is the same in all shared states, their multiplicity must coincide in all remaining shared states.
If there is a path between s 0 and shared state s in which the same events (and the same number of times but no matter in which order) are fired in both TSs A 1 and A 2 , then the condition is automatically satisfied. Only in the case where all paths are different, we say that shared state s is in conflict, and then we must explicitly enforce the equality of the multiplicity of s in both systems.
This condition can be expressed in matrix form using a row for each shared state in conflict (different than s 0 since this state is never in conflict). For a shared state s in conflict, its corresponding row will be of the form (r 1 (s) . . . r n (s) − q 1 (s) . . . q m (s)), where all regions r i and q j have been shifted, as said before, so that r i (s 0 ) = q j (s 0 ) = 0. Let us name as C the matrix containing such rows, we will call it the shared state conflict matrix between A 1 and A 2 . Now since the multiplicity of all these states must be the same, their subtraction must be 0. Thus, C • x = 0. Theorem 2. Let A 1 and A 2 be two compatible TSs with region bases {r 1 , . . . , r n } and {q 1 , . . . , q m } respectively. Let M be their gradient compatibility matrix, C be the shared state conflict matrix, and x the column vector of variables x 1 to x n+m . Consider an assignment to the variables in x such that M C • x = 0 and some x i = 0. This assignment identifies a region r q = 1≤i≤n r i x i 1≤j≤m q j x n+j in A 1 ∪ A 2 .
Proof. A non-trivial solution x defines two compatible regions, namely r = 1≤i≤n r i x i and q = 1≤j≤m q j x n+j , in A 1 and A 2 respectively. These two regions are compatible according to Definition 15 if M • x = 0, because for common events the gradient is the same and the offset is the same in all shared states if C • x = 0. By Proposition 2, r q is a region of
So the problem reduces to finding the solutions to a homogeneous linear system. Note that the system does not require to have solutions in the integer domain. In fact all the solutions are in Q, since all the gradients are integers. Homogeneous linear systems have one trivial solution (i.e. 0) and infinite nontrivial solutions. Let y i be all the non-redundant solution vectors, then any possible solution of the system can be obtained by linear combination of these solution vectors, since adding or subtracting 0 from 0 does not change its value. These y i are a basis of the nullspace of M C , and any solution x can be written as a unique linear combination x = i λ i y i , with λ i ∈ Q.
There are several well-known methods to obtain a basis for the nullspace [19], one of the easiest is to put the matrix in reduced row echelon form, determine the
Partial order ⊆ in A2 Fig. 8. Partial orders between combinations of regions in each subsystem, according to the subset relation on multisets (⊆).
Property 1) 3 . Thus, the strategy would be to test the basis combinations in the first subsystem, keeping only the combinations producing non-normalized regions. Then only these combinations will be tested in the second subsystem, discarding the ones that yield a normalized region, and the process will continue until all subsystems have been checked. Finally, with only the surviving combinations, the subregion test will be performed to guarantee that only the minimal regions are found. Again this test can be distributed among the subsystems, since i c i • b i ⊆ i c i • b i if, and only if, for all subsystem j, i c i • b j i ⊆ i c i • b j i . We will illustrate all this process using our running example. In Fig. 7 we can see a tree of combinations of the {b 0 , b 1 } basis. Each node is a tuple (c 0 , c 1 ) describing the coefficients used to obtain a region r as c 0 • b 0 + c 1 • b 1 . The second level of the tree corresponds to the regions in the basis and their coregions (as shown in Fig. 6). To bound the search space, assume we arbitrarily fix that the coefficients are only allowed to take values in the set {−1, 0, 1}.
From the four possible combinations in the third level, two of them yield already normalized regions in A 1 , namely combinations (1, 1) and (−1, −1). On the other hand, combinations (1, −1) and (−1, 1) correspond to non-normalized regions in A 1 , as shown in the figure. Consequently only these two combinations will be checked in subsystem A 2 . In this case, both regions, namely, b 2 0 + (−b 2 1 ) and −b 2 0 +b 2 1 , are also non-normalized in A 2 . Thus these combinations correspond to non-normalized regions in A 1 ∪ A 2 , which means that they might be minimal regions (once normalized). real bottleneck of some of the region-based techniques in the literature, methods like the one presented in this paper might represent a crucial step into making the theory applicable in industrial scenarios.