The quality of algorithms is often determined by benchmarking, i.e., testing the algorithm on a predetermined data set. In contrast to traditional benchmarking, with fixed data set, we present a way to generate random sets of test data. In this paper we present random classes of Petri nets and a method to generate finite samples from such a class. The classes may contain infinitely many Petri nets, each net with its own probability to be generated. This generation method is based on stepwise application of construction rules such as refinement rules. Each random class of Petri nets has a probability distribution for each of its characteristics. We illustrate the approach by estimating this distribution for some simple characteristics.
In computer science research we often lack a method to evaluate the quality of
an algorithm in an analytical way. The quality may concern the efficiency of the
algorithm (how fast is a solution found) or the effectiveness (how good is the
solution found). Although it is sometimes possible to give bounds for the worst
case behavior, it is seldom possible to determine the average-case behavior
analytically. What we normally do is fixing a set of test data as benchmark and
then we test the algorithm on that set, which is called benchmarking. Generally
a benchmark is either pre-defined or generated. Both have disadvantages [
In this paper we focus on Petri nets and algorithms to compute their
characteristic properties. Hence we define random classes of Petri nets. Such a class
contains Petri nets with some structural property, like free choice nets. There
may be infinite number of nets in one class. Each net in a class has its own
probability of being selected for a benchmark. Petri nets are used to model
complex processes [
Although our generation method for benchmarks can be applied to all kinds
of algorithms on Petri nets, we use it here to determine characteristics of the
random classes of Petri nets. Simple examples of such characteristics are the
number of nodes, and the average fanin and fanout of nodes. More complicated
ones are the occurrence (or the number) of deadlocks or livelocks. Each
characteristic of a Petri net is expressed by a real number. In some cases we consider
only 0 and 1 and we consider them as ’false’ and ’true’. Since every Petri net in a
class has a certain probability of being selected in a benchmark, we may consider
every characteristic as a random variable having a probability distribution over
the class. For the given examples, we can speak of the expectation and variance
of the number of nodes in a class, or the probability of having a deadlock. We
have developed a software tool in the form of a plugin for ProM (cf [
The rest of this paper is organized as follows. Section 2 introduces the necessary preliminaries. In Section 3 we represent our construction rules and discuss our methodology of generating Petri nets. Section 4 presents some characteristics. The software tool is introduced in Section 5 with characteristic examples. Related work is discussed in Section 6. Finally Section 7 concludes this paper and discusses some of our future researches on identifying class parameters. 2
Let S be a set. With |S| we denote the number of elements in S. The empty set, e.g., the set without any elements is denoted by ∅. Two sets S and R are disjoint
if S ∩ R = ∅. We denote the set of all natural numbers as N = {0, 1, 2, · · ·}. A sequence σ of length l ∈ N over S is a function σ : {1, · · ·, l} → S. We denote a sequence by σ =< σ(1), σ(2), ···, σ(l) >, such that ∀i(1 ≤ i < l) : σ(i) ∈ •σ(i+1).
σ We write here this as n1 −→ nl. We denote the length of a sequence by |σ|. The set of all finite sequences over S is denoted as Σ. Let ν, γ ∈ Σ be two sequences. Concatenation, denoted by σ = ν ◦ γ, is defined as σ : {1, · · ·, |ν| + |γ|} → S, such that for 1 ≤ i ≤ |ν| : σ(i) = ν(i), and for |ν| + 1 ≤ i ≤ |ν| + |γ| : σ(i) = γ(i − |ν|). The Parikh vector of a sequence σ, denoted by →−σ, is a bag representing the number of occurrences of each element in σ. A bag m (multiset) over S is a function m : S → N. For s ∈ S, m(s) denotes the number of occurrences of s in m. We denote a bay by square brackets. e.g., in a bag [a, b2, c], element a occurs once, element b twice, and element c once. All other elements have a multiplicity of 0. ≺ is the prefix operator, such that σ0 ≺ σ if and only if ∃σ00 : σ = σ0 ◦ σ00 .
A Petri net is a tuple N = (P, T, F ) where P is the set of places, T is the set of transitions, P and T are disjoint, and F ⊆ (P × T ) ∪ (T × P ) is the set of arcs. An element of P ∪ T is called a node. We call an element of P ∪ T ∪ F is an element of N . A path in N is a sequence σ over the set P ∪ T . Graphically, we denote places by circles, transitions by squares, and arcs as arrows between places and transitions. The state of a Petri net, called a marking is a bag over the places P of N . A marking is graphically represented by placing tokens in each place. A marked Petri net is a pair (N, m0), where N is a Petri net and m0 is a marking of N . A transition t ∈ T is enabled in (N, m0), denoted by t (N : m0 →−) if •t ≤ m0. An enabled transition in (N, m0) can fire resulting in a t new marking m0 = m0 − •t + t•, denoted by (N : m0 →− m0 ).
A special class of Petri nets are workflow nets. A workflow net is a 5-tuple W = (P, T, F, i, f ) where (P, T, F ) is a Petri net, i ∈ P is the initial place, such that •i = ∅, f ∈ P is the final place, such that f • = ∅, in graph of W each node n ∈ P ∪ T is on a directed path from i to f . If for a workflow net W , we have ∀p ∈ P \ {i, f }, |p • | = | • p| = 1, |i • | = | • f | = 1, the workflow net is a T-net, also called a marked graph workflow net. If ∀t ∈ T, |t • | = | • t| = 1, then it is a S-net, also called a state machine workflow net. In a workflow net, two places p, s ∈ P , if either p• = s• or p • ∩s• = ∅, then this workflow net is a free-choice workflow net. A firing sequence or a trace is a sequence σ over T such that all the transitions of σ can fire in that order starting from the initial marking. A trace for a workflow net is complete if it leads to the final marking with only f marked.
A workflow net is k sound, for k ∈ N if for each marking m that is reachable
from an initial marking m0 with only k tokens in the initial place i, the final
marking with only k tokens in the final place f can be reached. A workflow net
is generalized sound if it is k-sound for all k ≥ 1 ([
In this section we firstly define the construction rules. The rules enable us to generate all Petri nets, here we focus upon workflow nets. Moreover, we show that different subclasses of workflow nets can be generated by different construction rules. Finally, we discuss our method of randomly generating Petri nets. 3.1
Based upon how they can modify the structure of Petri nets, the construction
rules are divided into two classes, refinement rules and bridge rules. The
refinement rules ([
Refinement rules. Figure 1 is an example of the refinement rules. Definition 1 (Place refinement rule R1). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR1 if and only if there exist places s, r ∈ P 0 , s 6= r and a transition t ∈ T 0 such that: •t = {s}, t• = {r}, s• = {t}, •s 6= ∅, •s 6⊆ •r. The net N satisfies: P = P 0 \ {s}, T = T 0 \ {t}, F = (F 0 ∩ ((P × T ) ∪ (T × P ))) ∪ (•s × t•).
Definition 2 (Transition refinement rule R2). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR2 if and only if there exist a place s ∈ P 0 and transitions t, u ∈ T 0 , t 6= u such that: •s = {u}, s• = {t}, •t = {s}, t• =6 ∅, u• 6⊆ t•. The net N satisfies: P = P 0 \ {s}, T = T 0 \ {u}, F = (F 0 ∩ ((P × T ) ∪ (T × P ))) ∪ (•u × s•).
Definition 3 (Arc refinement rule R3). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR3 if and only if there exist two nodes m, n ∈ P 0 ∪ T 0., TsuhcehntehtaNt: s|a•timsfi|es=: P1,∪mT•==(P{0n∪},T |n)\•{|m=,n1},, •n = {m}, (•m × n•) ∩ F 0 = ∅ 0 F = (F 0 ∩ ((P × T ) ∪ (T × P ))) ∪ (•m × n•).
Note that in Figure 1, R3 shows only one instance of the arc refinement rule. We can also refine any arc with a place as its source node and a transition as its target node. This case is not shown in Fig 1.
Definition 4 (Place duplication rule R4). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR4 if and only if there exist tPwo= pPlac\es{ss},,rT∈=PT0 ,0 s, F6==r Fsuc∩h (t(hPat×: •T ) ∪ (T × P )).
s = •r, s• = r•. The net N satisfies: 0 0 Definition 5 (Transition duplication rule R5). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR5 if and only if there exist two transitions t, u ∈ T 0 , t 6= u such that: •t = •u, t• = u•. The net P = P 0 , T = T 0 \ {u}, F = F 0 ∩ ((P × T ) ∪ (T × P )).
Definition 6 (Loop addition rule R6). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR6 if and only if there exists a place s ∈ P 0 and a transition t ∈ T 0 such that: •t = {s}, t• = {s}. The net N satisfies: P = P 0 , T = T 0 \ {t}, F = F 0 ∩ ((P × T ) ∪ (T × P )).
Bridge rules. Figure 2 is an example of the bridge rules.
Definition 7 (Place bridge rule R7). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR7 if and only if there exist one place satisfie0sa:nPd =twPo 0tr\a{nss}it,ioTns=uT, t0,∈FT=0 sFu0c∩h (t(hPat:וTs)=∪{(uT}×,sP )). s ∈ P • = {t}. The net N Definition 8 (Transition bridge rule R8). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR8 if and only if there exist one transition t ∈ T 0 and two places s, r ∈ P 0 such that: •t = {s}, t• = {r}. The net N satisfies: P = P 0 , T = T 0 \ {t}, F = F 0 ∩ ((P × T ) ∪ (T × P )). Definition 9 (Arc bridge rule R9). Let N = (P, T, F ) and N 0 = (P 0 , T 0 , F 0 ) be two Petri nets. We say (N, N 0 ) ∈ ϕR9 if and only if there exist two nodes s, r ∈ P 0 ∪ T 0 , such that (s, r) ∈ F 0 . The net N satisfies: P = P 0 , T = T 0 , F = F 0 \ {(s, r)}.
Note that in Figure 2, R9 merely shows one instance of the arc bridge rule. We can also bridge a place and a transition with an arc. This case is not shown in Figure 2.
In R8, if s and r are the same place, it becomes R6. Thus the loop addition
rule R6 is a special case of the transition bridge rule R8. All the refinement rules
(R1,...,R6) preserve liveness and boundedness properties of Petri nets (with
respect to a given marking) (proofs can be found in [
In this part we study different classes of the generated Petri nets based on their
structures. We focus on workflow nets and their subclasses, namely, Jackson
nets, state machine workflow nets, marked graph workflow nets, and free-choice
workflow nets. These workflow nets without Jackson nets are defined in Section
2, so firstly we define a Jackson net as follows. For a formal description and
analysis of Jackson nets see [
Definition 10 (Jackson net). A Jackson net is a workflow net that can be generated, from one single place, by applying the rules R1, R2, R4, R5, and R6 recursively. However, only the rule R1 can be applied in the first step, and no rules can be applied to the initial place and the final place after the first step.
In order to generate all workflow nets (starting with two places), it is sufficient to use the arc refinement rule R3 and the bridge rules R7, R8, R9 only. To prove that, we give the following definition.
Definition 11 (Copy of a net). Let N be a workflow net. N 0 is a copy of N if and only if there is a bijection ϕ such that ϕ(P ) = P 0 , ϕ(T ) = T 0 , ϕ(F ) = F 0 and ∀(x, y) ∈ F : ϕ((x, y)) = (ϕ(x), ϕ(y)).
A path taken from a Petri net defines a new Petri net, so copying a path can be treated as copying its corresponding Petri net.
Lemma 1. Given two nodes, m1, m2 ∈ P ∪ T , and a path σ, such that m1 = σ(1), m2 = σ(|σ|), and ∀i ∈ dom(σ) : →−σ(i) = 1. Then we can copy σ by firstly applying a bridge rule on (m1, m2) and afterwards repeating the arc refinement rule.
Lemma 2. We have a path σ in a Petri net, if there is some node n such that →−σ(n) > 1, then there is a path σ0 = σ1 ◦ σ3 if and only if σ = σ1 ◦ σ2 ◦ σ3 and n −σ→2 n.
Theorem 1. Let N be a workflow net. Then N can be copied into N 0 by only using the bridge rules and the arc refinement rule, starting with only two places. Proof. Initially P 0 = {i0 , f 0 }, T 0 = ∅, F 0 = ∅, i0 = ϕ(i), and f 0 = ϕ(f ). We select an arbitrary node n from N such that n ∈ P ∪ T and n 6∈ P 0 ∪ T 0 . In N , from n we find two paths, n1 −σ→1 n and n −σ→2 n2, such that n1, n2 ∈ P 0 ∪ T 0 and all other nodes on σ1 and σ2 are not in P 0 ∪ T 0 . This is always possible by the definition of a workflow net. By Lemma 2 we can reduce σ1 and σ2 by removing all internal loops along the paths.
Consider case (1): suppose σ1 and σ2 have no common internal nodes, then we may apply Lemma 1 by adding the path σ1 ◦ σ2 from n1 to n2, and add n0 = ϕ(n) to the copy.
Consider case (2): suppose σ1 and σ2 have common internal nodes, e.g., ∃i, j : σ1(i) = σ2(j) 6= n, then there is a loop. We then look for the first node m on σ1 which is also on σ2. Then ∃σ3, σ4, σ5, σ6 : n1 −→ m −σ→4σ3n ∧ n −σ→5 m σ−σ6→6 n2 σ3 where σ1 = σ3 ◦ σ4 and σ2 = σ5 ◦ σ6. Now we have found n1 −→ m and m −→ n2, and σ3 and σ6 have no internal nodes in common as m is the first common node on σ1. We replace n with m, then we apply Lemma 1 by adding the path σ3 ◦ σ6 from n1 to n2, and we add node m0 = ϕ(m) to the copy.
In each step, therefore, we add at least one node. We repeat this procedure until all the nodes of N are copied into N 0 . Finally, we add all arcs F \ ϕ−1(F 0 ) by arc bridge rule. Now N 0 is a copy of N . tu
Now let us consider which rules allow us to generate the subclasses of workflow nets. Based upon Theorem 1, it is easy to prove that we only need the transition bridge rule and the arc refinement rule to generate all state machine workflow nets, and we need the place bridge rule and the arc refinement rule to generate all marked graph workflow nets. They yield Corollary 1 and Corollary 2. As defined in Definition 10, Jackson nets are generated by the rules R1, R2, R4, R5, and R6. For a free-choice workflow net, the rules R1, R2, R4, and R5 can always preserve its properties.
Corollary 1. If N is a state machine workflow net, then N can be copied into N 0 by only using the transition bridge rule with the arc refinement rule. Corollary 2. If N is a marked graph workflow net, then N can be copied into N 0 by only using the place bridge rule with the arc refinement rule. Theorem 2. The place refinement rule, the transition refinement rule, the place duplication rule, and the transition duplication rule preserve the free-choice workflow net property.
[
Our approach of generating Petri nets has two determinants, construction rules and probabilities of the rules. We have discussed the necessary rules to generate different classes of workflow nets. In this part, we focus on the probability-based rule selection.
Given two nets N and N 0 , we say that N generates N 0 if and only if N 0 can be obtained from N by applying zero or more times a rule from our construction rules. To generate a workflow net we adopt a stepwise refinement technique starting with one single place. In the first step we apply the place refinement rule to generate the initial place and the final place. For any subsequent steps, we select a rule from all the rules whose conditions hold (we say those rules are enabled ). For the initial and the final places there are some restrictions such that the place refinement rule, the place duplication rule, the loop addition rule cannot be applied to the initial and the final places, and for the transition bridge and the arc bridge rules, the initial place cannot be the target place (i.e., r in Definition 8 and 9), and the final place cannot be the source place (i.e., s in Definition 8 and 9). Figure 3 depicts an example of net refinement.
In order to select a rule from all the enabled rules, we attach a rule weight to each rule. A rule weight is a random number ranging from 0 (least likely) to 100 (most likely). Therefore, a rule is randomly selected based on the rule weight. Similarly, we also attach an element weight (also ranging from 0 to 100) to each of the elements (each of the places, transitions, and arcs) in a net. Hence each rule can randomly select an element or a pair of them based on the element weight to expand a net. Because we always start with an initial net to generate another net, for all the elements in the initial net, we give each of them a default element weight. When we apply rules, new elements are added into the net. In
Fig. 3. An Example of Workflow Net Refinement order to determine weights of the newly added elements, we define three type parameters (ranging from 0 to 1) for each element type, namely, place parameter, transition parameter, and arc parameter. Each rule can have some or all of the type parameters based on what kinds of elements it can introduce. For instance, as the place refinement rule can introduce two places, a transition, and two arcs, the rule has all the type parameters. While, the place bridge rule can add a place and two arcs, so it only has the place parameter and the arc parameter. All the refinement rules (R1,...,R6) only refine one element, so the weight of the newly added elements are determined by the multiplication of the weight of the refined element and the type parameters. For example, if we refine a place having a weight of 50, and we let the place parameter be 0.2, the transition parameter be 0.5, and the arc parameter be 0.1, then any newly added place has a weight of (0.2 x 50 =) 10, any newly added transition has a weight of (0.5 x 50 =) 25, and any newly added arc has a weight of (0.1 x 50 =) 5. On the other hand, all the bridge rules bridge a pair of nodes, so the weight of the newly added elements are determined by the multiplication of the sum of the bridged nodes and the type parameters. For instance, if we bridge two transitions having a weight of 50 and 70, respectively, then any newly added place has a weight of ((50 + 70) x 0.2 = ) 24, and any newly added arc has a weight of ((50 + 70) x 0.1) = 12.
Therefore, such a mechanism makes net generation random. We are currently considering other mechanisms besides this one as well. 4
Characteristics of Petri nets in different classes are decidable with the generated benchmarks. Such characteristics we consider currently consist of length of the shortest path (number of transitions in a path is the length of this path), number of nodes, average number of fanin and fanout of nodes, deadlock and livelock, and coverage. We use a real number to express each characteristic, in some cases we use 1 for true and 0 for false. Each Petri net in a class has a certain probability of being selected in a benchmark, and each characteristic can be considered as a random variable having a probability distribution over that class. For instance, with the given samples from a class, we can speak of the expectation and variance of the number of nodes in the class, or the probability of having a deadlock. Therefore, we can estimate the characteristics of any new nets from the same class with ceratin confidence. In this section, we focus on the characteristic coverage and give two examples to illustrate how it can help in testing.
We restrict ourselves to a Petri net with an initial node such as a workflow net. Each transition in the net is attached with a label. The goal of the coverage test is to find all the transitions with a certain label. The coverage is measured by trace coverage and transition coverage. We start a path with the initial node, at each choice point we select one of the enabled transitions at random. As soon as we find a transition with the label that we look for, we stop and start a new trace from the initial node again. Therefore, the trace coverage is the number of traces that we need to find all the transitions with the label, and the transition coverage is the number of transitions fired to find all the transitions with the label. We show two applications of how to use the coverage in testing.
Finding labels. We may attach labels to transitions in a workflow net. In this application we need to find all the transitions with a special label. We start in the initial state. A transition is randomly fired when there are two or more enabled transitions. After a transition has fired, we test whether it has the special label. If so we remove this label and we start a new trace from the initial state again. Otherwise we continue until we reach the final state and then we start from the initial state again. We stop if all the transitions with the label have been found. The coverage returns the number of traces followed and the number of transitions fired in order to find all the labeled transitions. Algorithm 1 describes this application. In this algorithm all transitions have a label either 0 or 1. We are looking for the transitions with label 1.
As labeling can be associated with different concepts, this algorithm can be
used in model-based software testing as done in [
Finding causal pairs. In this example we test how long (measured in coverage)
it takes to cover all the causal pairs, i.e., a possible pair of consecutive transitions,
in a workflow net. For process miners, i.e., the alpha algorithm [
Algorithm 1: Finding Labels input : a sound N = (P, T, F, i, f ) output: pathCoverage, transitionCoverage an estimate of the length of a log in order to be complete for random classes of Petri nets.
Finally, we show the result of an empirical study we did. We used the tool we developed (see Section 5) to randomly generated 3000 well-structured workflow nets. Those nets were used as benchmarks to get the results in Table 1. 5
We realized a supporting tool for our methodology. The tool is developed as a
plugin for the ProM framework [
Graphical user interface. Figure 4 is a snapshot of the tool interface.This graphical user interface is easy to use. For example, it lists all the rules visually so that it is very intuitive for the user to select a particular rule. The generated nets can be visualized using the viewer provided by ProM. Testing results are output in a table for the user.
Selection of net class. The interface contains all the classes of the workflow nets that the user can generate. Once a particular class has been selected, all the rules which are not allowed in such a class are disabled automatically by giving their probabilities a value of zero. 4 5 end
Algorithm 2: Finding Causal Pairs input : a sound N = (P, T, F, i, f ), a set C of all the causal pairs in N output: pathCoverage, transitionCoverage
Random weight of rules. The user can change the weight of any enabled rule using the sliding bar under the rule image, the probability of the rule is calculated and displayed next to the sliding bar.
Specification of sample size and net size. The user can specify the number of nets to generate and the number of times to apply rules to generate a net. The sizes of all nets have a poisson distribution, the user only needs to input the average number, then the tool is able to calculate the size of each individual net.
Selection of characteristics. The user can select the characteristics introduced in Section 4 to investigate the nets.
Reusability of samples. The tool saves all the generated nets in PNML format in a dedicated folder on disk. This enables the user to reuse or share any benchmarks.
[
In [
In this paper, we defined a graph grammar with weights on the construction rules, such that each graph of the graph language has a ceratin probability of occurring. We consider graphs in the form of Petri nets, and the generated Petri nets can be used as benchmarks. By extensive studies, we have a set of construction rules to generate all Petri nets with different starting nets using a stepwise refinement approach. Based upon structures, the nets can be classified into different classes. Each Petri net in a class has a certain probability to be selected in a benchmark. Moreover, we distribute weights to the rules and all elements in a net, this makes the generation random. We have determined a number of characteristics used in the random classes of Petri nets, and we are able to get probability distributions of each characteristic over the classes. We focused upon an interesting characteristic called coverage, and presented two possible applications of it. A tool has been developed in ProM to realize our methodology.
In future research, we would like to identify the probability parameters based upon a concrete set of process models in a statistical way. If we have the parameter we can do better benchmarking. Also we would like to distribute our tool over grid so that we can generate a large number of benchmarks.