Dipartimento di Informatica
Corso di Laurea Magistrale in Informatica (Classe LM-18)
A TOOL FOR CONFUSION REMOVAL
IN PROBABILISTIC CONCURRENT
MODELS
LAUREANDO Gianluca Maraschio
RELATORE Prof. Roberto Bruni
CONTRORELATRICE Prof.ssa Francesca Levi
1 LIST OF CODES
Code 2.1 Petri net definition in PNML language. ... 28
Code 2.2 Graph definition in DOT language. ... 29
Code 4.1 Assigning identifier for upper triangular reduction ... 44
Code 4.2 Computing the scalar product between a matrix and a vector ... 46
Code 4.3: Computing the product between two matrices ... 47
Code 4.4 Inefficient computation of the transitive closure of a general matrix. ... 47
Code 4.5:Efficient computation of the transitive closure of a general matrix ... 48
Code 4.6 Computing the transitive closure of a symmetric matrix ... 49
Code 4.7 Computing the set of maximal transactions of a node. ... 50
2 LIST OF FIGURES
Figure 1.1: Asymmetric confusion. ... 9
Figure 1.2: Confusion-free. ... 9
Figure 1.3: s-cells decomposition. ... 10
Figure 1.4 Confusion-free with s-cells. ... 10
Figure 2.1 Petri net with symmetric confusion ... 16
Figure 2.2 Petri net with asymmetric confusion ... 16
Figure 2.3 Dynamic p-net ... 19
Figure 2.4 The corresponding p-net(⦃N⦄) ... 19
Figure 2.5 Structural branching cells ... 22
Figure 2.6 Removing places from s-cell ... 22
Figure 2.7 Encoding of branching cells ... 24
Figure 2.8 Petri net in Woped ... 28
Figure 2.9 Drawing of graph written in DOT ... 30
Figure 3.1 self-conflict ... 33
Figure 3.2 Two different petri nets producing the same s-cell C1... 35
Figure 3.3 Two Petri nets with the same set of transitions. ... 35
Figure 3.4 flattening of a positive transition t ... 36
Figure 3.5 flattening of negative transition t ... 37
Figure 3.6 Petri net representation ... 39
Figure 3.7 Petri net representation with unary and binary relations. . 40
Figure 4.1 Acyclic graph G ... 44
Figure 4.2 first screenshot of the execution of the algorithm on the graph G ... 45
Figure 4.3 second screenshot of the execution of the algorithm on graph G... 45
Figure 4.4 Termination of the algorithm on graph G ... 45
Figure 4.5 Computing the maximal transactions of a place ... 51
Figure 4.6 A wrong attempt to compute the set of maximal transactions of a transition ... 52
3
Figure 4.8 Association with multiplicity 0,1 ... 54
Figure 4.9 Generalization ... 54
Figure 4.10 Dependency arrow ... 54
Figure 4.11: Class Diagram of parser package... 55
Figure 4.12 Class diagram of the representation package ... 56
Figure 4.13 Class diagram of the bitstructures package: matrix hierarchy ... 57
Figure 4.14 Class diagram of the bitstructures package, vector hierarchy ... 60
Figure 4.15 Class Diagram of the petrinet package ... 61
Figure 4.16 Class diagram of the dynamicPetriNet package ... 62
Figure 4.17 Class diagram of the persistentpetrinet package .. 64
Figure 4.18 Class diagram of the output package ... 66
Figure 4.19 Class diagram of the processing package ... 67
Figure 5.1 Confusion-free p-net in DOT... 73
Figure 5.2 Confusion-free p-net in PNML ... 73
Figure 5.3 Test 2: Petri Net with symmetric confusion ... 74
Figure 5.4 Test 2: Confusion-free p-net in Graphviz ... 76
Figure 5.5 Test 2: Confusion-free p-net in Woped ... 76
Figure 5.6 Test 3: Petri Net with confusion ... 78
4 CONTENTS 1 INTRODUCTION... 7 1.1 THESIS ORGANIZATION ... 12 2 BACKGROUND ... 13 2.1 BASIC NOTATION ... 14
2.2 PETRI NET AND CONFUSION ... 15
2.3 DETERMINISTIC NONSEQUENTIAL PROCESSES ... 17
2.4 NETS WITH PERSISTENCY ... 18
2.5 DYNAMIC NETS... 19
2.6 STRUCTURAL BRANCHING CELLS ... 21
2.7 ENCODING S-CELLS AS CONFUSION-FREE DYNAMIC NETS 23 2.8 TECHNOLOGIES ... 26
JAVA LANGUAGE ... 26
PNML FORMAT ... 26
DOT FORMAT ... 29
3 REQUIREMENTS AND SOFTWARE ARCHITECTURE ... 31
3.1 REQUIREMENT ANALYSIS ... 32
Reading the petri net given as input ... 32
Representing a petri net through suitable data structures ... 32
Checking if the Petri net satisfies the desired requirements .... 33
Encoding the petri net into a dynamic petri net ... 34
Flattening dynamic nets, by adding persistent places ... 36
Outputting the corresponding confusion free-net ... 37
3.2 ARCHITECTURE ... 39
4 IMPLEMENTATION ... 42
4.1 IMPLEMENTED ALGORITHMS ... 43
Upper triangular reduction ... 43
Scalar product between a matrix and a vector ... 46
Product between two matrices ... 46
5
Transitive closure of a symmetric matrix ... 48
Computing the set of maximal transactions of a s-cell ... 50
4.2 CLASS DIAGRAMS ... 54 PARSER ... 55 REPRESENTATION ... 56 BITSTRUCTURES ... 57 PETRINET ... 61 DYNAMICPETRINET ... 62 PERISTENPETRINET ... 64 OUTPUT ... 66 PROCESSING ... 67 5 RESULTS ... 69
5.1 Test 1: Asymmetric confusion ... 71
5.2 Test 2: Symmetric Confusion ... 74
5.3 Test 3 ... 78
6 CONCLUSION ... 80
6 ABSTRACT
Concurrency and probability are two important features of modern ICT systems, models and languages.
The study of concurrent models where decisions are driven by proba-bilistic distribution is complicated by the so-called confusion problem. It arises when an event increases or decreases the set of alternatives for another concurrent event that is already enabled.
The confusion problem interferes with concurrency, in the sense that, equivalent computations from point of view of concurrency, can be as-signed different probabilities.
In a recent paper it has been shown that confusion can be removed by identifying the loci of decisions and introducing additional dependen-cies between events.
In the thesis we develop a tool for the automatic and compositional syn-thesis of confusion free models, exploiting the theory developed there. The tool, developed in Java language, receives in input a Petri net (in a suitable class), removes automatically confusion, and produces in out-put the corresponding transformed Petri net.
The format file for exchanging Petri nets that we use is a standard XML dialect called PNML. Therefore, our tool reads a PNML representing Petri net to transform and outputs another PNML file describing the corresponding Petri net without confusion.
The output Petri net will be described also in DOT format, mainly for a better rendering of its graphical layout.
7 1 INTRODUCTION
Nowadays, modern ICT systems are mostly concurrent. Moreover, there is a rapidly growing interest in probabilistic programs due to their extensive use in various fields like security, biology, machine learning, approximate and quantum computing.
Unfortunately, adding probabilities in presence of concurrency and nondeterminism is not trivial [1]. The challenge is to assign a truly con-current semantic that is coherent with probability distribution. A com-putation (i.e. process) is truly concurrent, if it is an equivalent class of interleaved executions, where the order of concurrent events doesn’t matter. Also, a semantic is coherent if the following criteria are satisfied [2]:
1. speed independence: computation must be independent of the time and speed of processors;
2. pure probabilistic computation: nondeterminism must be fully replaced by probabilistic choice;
3. schedule independence: the probability distribution that drives the choice of a certain computation must not be affected by the execution of other concurrent computations;
4. complete concurrency: it should be possible to establish a bijec-tive correspondence between processes and equivalence classes of sequential computations;
5. the probability of a concurrent computation must be independ-ent of the order of execution of its concurrindepend-ent evindepend-ents;
6. the sum of the probabilities assigned to all maximal processes must be 1.
One of the main problems about defining a coherent semantic is dealing with confusion, which compromises items 3,5,6 above.
Confusion naturally arises in concurrent and distributed systems and is intrinsically present in problems involving mutual exclusion. It can be considered as a main open problem for concurrency theory.
As an example of confusion, suppose that a system is composed of two agents x and y. Agent x can choose to execute actions a or b and agent y can choose between actions c or d, but action c can be executed only after b. In this case, the probability distribution which drives the y’s choice is influenced by the choice of agent x (if agent x chooses action a,
8
agent y has the only possibility to execute d). A process that includes actions b and d can be executed independently from the order of ac-tions, but their order influences the probability of its execution. In fact, Let P(b) the probability to choose b over a, and P(d) the probability to choose d over c. Then, the probability to execute d after b is the product between P(b) and P(d); while executing b after d has P(b) as probability because before executing b, the only possibility for y is to execute d. In this work we focus on Petri nets. In particular, we study how concur-rency and probability can interact in Petri nets.
Petri nets are computational models suitable for analysing concurrency. They are the ideal ground to study the problem, thanks to their simplic-ity and extendibilsimplic-ity.
In Petri nets agents and actions are represented as places and transi-tions, respectively. Instead, processes are equivalence class of firing se-quences of transitions. In Petri nets, the confusion arises when the set of alternatives to an enabled action (transition) decreases or increases by the firing of an independent transition.
The addition of the probability to Petri nets has been extensively stud-ied in the literature. In [3], the authors focus just on confusion-free nets. In [4], the authors solve confusion globally by considering event struc-tures rather than Petri nets. Their result is a substantial advance in the study of concurrent and probabilistic models. Despite this, an improvement on last work has been made recently in [2] and precisely on this, the thesis is based.
The solution in [2] provides a positive answer to the confusion removal problem for the case of finite occurrence nets (nets without cycles) and it arises from the following intuition: if the execution of a transition in-fluences a choice in another point of the net, then the choice must be taken after the end of the execution of the transition. Then, it is neces-sary to introduce additional causal dependencies between transitions that enforce a suitable ordering of executions. Referring to the previous example, the idea is to delay the choice of y until the choice of x has been made.
As a practical situation imagine that you have to decide whether to go to the theatre alone (d) or with your girlfriend (c). The last option is only possible if she chooses to come to the city (b), instead of staying at home (a). So before making a decision, it would be better to wait for your girlfriend’s decision.
This situation is faithfully represented by diagrams in Figure 1.1 where you don’t wait for your girlfriend’s decision, and in Figure 1.2 where in-stead you wait for her.
9
In the figures, a wavy line between two events means that one conflicts with the other. Also, an arrow from an event to another event repre-sents causality: it means that the latter can be executed only after the former (execution dependency).
Figure 1.1: Asymmetric confusion. b and c are respectively in conflict with a and d; c can be executed only after b
Figure 1.2: Confusion-free. d2 and c are in conflict and can be executed only after b; d1 can be exe-cuted only after a that conflicts with b.
In the confusion-free case (Figure 1.2) there are two versions of d (go-ing to the theatre alone): d1(go(go-ing to the theatre alone because she’s not in the city) and d2 (going to the theatre alone although she’s in the city)
The paper [2] shows how to translate nets with confusion to confusion free nets.
The developed procedure consists of the following steps:
i. recursively and statically decompose the Petri net, into smaller subnets called s-cells (Structural Branching Cells), as shown in Fig-ure 1.3 (s-cells are represented with dashed boxes);
ii. derive a confusion-free Petri net by combining s-cells with each other, as in Figure 1.4.
An s-cell C is uniquely determined by a set of transitions that are causally related to each other. Each s-cell exposes a set of alternatives, called transactions that can be equipped with a general probability dis-tribution. A transaction, or equivalently a process, consists of a set of transitions that compose a set of firing sequences.
Each s-cell is subdivided, in turn, into other sub s-cells by considering the disappearance of alternatives from the cell. In Figure 1.3 sub s-cell C3 is created from C2 by considering the disappearance of the alter-native c.
The derivation of a confusion-free net is done by exploiting the encod-ing of s-cells in dynamic nets and by composencod-ing them accordencod-ing to the causality relation.
d c a b
d2 c d1
10
Figure 1.3: s-cells decomposition. s-cells are identified with C1, C2 and C3
Figure 1.4 Confusion-free with s-cells.
In the confusion-free net (Figure 1.4) there are two versions of d: d1 and
d2 which belong to s-cells C3 and C2, respectively.
In net with confusion (Figure 1.1 and Figure 1.3) the firing of b increases the alternatives to the enabled transition d. In confusion-free net (Fig-ure 1.2 and Fig(Fig-ure 1.4) d, with its two versions (d1 and d2), is enabled only after the choice to execute either b or a has been taken.
From the concurrency point of view, the following processes occur in the confusion-free model:
• a process that comprises both a and d1 (with a that causes d1)
whose overall probability is the probability of choosing a instead of b;
• a process that comprises b and d2 (with b that causes d2), whose
overall probability is the product of the probability of choosing b over a and that of choosing d over c
• a process that comprises b and c (with b that causes c), whose overall probability is the product of the probability of choosing b over a and that of choosing c over d.
In summary, the original net is translated into another net whose places (agents) are those of original net, and whose transitions (actions) are the transactions of s-cells with the addition of auxiliary elements. The resulting net is a confusion-free model, namely if a transition is enabled, then all its conflicting alternatives are enabled or definitively disabled. The work of thesis consists of developing a tool using Java language that, given a class of Petri net as input, removes automatically confusion from it by applying the procedure explained above. The output net ob-tained from the tool will be the corresponding confusion-free Petri net.
d c a b C1 C2 C3 C1 b a c d2 C2 C3 d1
11
The file formats handled by the tool are principally PNML and DOT: the first one is used specifically to describe Petri nets, while the second one to describe any graph.
We describe input and output Petri nets through PNML since tools that handle this format, in addition to display the represented Petri net graphically, show its semantic by evincing all its possible firing se-quences.
These tools view the Petri net by placing the nodes in the graphical space according to their coordinate specified in PNML. Assigning coor-dinates to nodes of the output Petri net results to be a difficult task. A software, called Graphviz, helps us: it automatically assigns to each node of a graph, described in a DOT file, a coordinate, so that any graph viewer tool can display the graph with an orderable and understanda-ble layout.
Therefore, our tool first outputs a DOT file representing the computed Petri net. Then, the file is processed by Graphviz tool. The coordinates of nodes specified in the final output PNML file will be those automati-cally computed by Graphviz tool.
12
1 . 1 T H E S I S O R G A N I Z A T I O N
The remainder of the thesis is organized as follows:
− Chapter 2 describes the background necessary to understand the work done in the thesis;
− Chapter 3 describes the requirements analysis and the architec-ture of the tool developed;
− Chapter 4 gives an overview of how our tool is implemented; − Chapter 5 contains some examples of the execution of the tool − Chapter 6 contains the conclusions and future work
13 2 BACKGROUND
In this part, we first describe basic background that will pose the pillars for later detailed concepts. We start by fixing basic notation and then by defining static, dynamic and persistent Petri nets and how these are generated. This material is mostly taken from [2].
Finally, we illustrate the main technologies used, like the Java program-ming language and the file formats PNML and DOT.
14
2 . 1 B A S I C N O T A T I O N
We let N be the set of natural numbers, N∞=N ⋃ {∞} and 2 = {0,1}. We
write US for the set of functions from S to U: hence a subset of S is an
element of 2S, a multiset m over S is an element of NS, and a bag b over
S in an element of (N∞S).
By overloading the notation, union, difference and inclusion of sets, multiset and bags are all denoted by the same symbols: ⋃, \ and ⊆ re-spectively. In the case of bags, the difference b\m is defined only when the second argument is a multiset, with the convention that (b\m)(s)=∞ if b(s)=∞.
Similarly, (b⋃b’)(s)=∞ if b(s)=∞ or b’(s)= ∞. Sometimes we view a set as a multiset or a bag whose elements have unary multiplicity. Mem-bership is denoted by ∈: for a multiset m (or a bag b), we write s∈m for m(s)≠0(b(s)≠0).
Given a binary relation R⊆S X S, we denote by R+ and R* its transitive
15
2 . 2 P E T R I N E T A N D C O N F U S I O N
A Net structure N (also Petri net) [5, 6] is a tuple (P,T,F) where: P is the set of places, T is the set of transitions, and F ⊆ (P X T)⋃(T X P) is the flow relation. For x∈ P ⋃ T, we denote by •x={y|(y,x)∈F} and x•={z|(x,z)∈F} its preset and postset, respectively. We assume that P and T are disjoint and non-empty and that •t is non-empty for every t ∈ T. We write t: X →Y for t ∈T with X=•t and Y= t•.
A marking is a multiset m∈ NP. We say that p is marked at m if p∈ m. We
write (N,m) for the net N marked b m. We write m0 for the initial
mark-ing of the net, if any.
Graphically, a petri net is a directed graph whose nodes are the places and transitions and whose set of arcs is F. Places are drawn as circles and transition as rectangles. The marking m is represented by inserting m(p) tokens in each place p∈ m.
A transition t is enabled at the marking m, written m →, if •t ⊆m. The t execution of a transition t enabled at m, called firing, is written m → m’, t with m’=(m\•t). A firing sequence from m to m’ is a finite sequence of firings m = m0
t1
→∙∙∙→ mtn ′, or just m→ m’. Moreover, it is maximal if no ∗ transition is enabled at m’. We say that m’ is reachable from m if m
∗
→ m′. The set of markings reachable from m is written [m⟩. A marked
net (N,m) is safe if each m′ ∈ [m⟩ is a set. Two transitions t, u are in direct conflict if •t ∩ •u ≠ ∅.
A marked net (N, m0) has confusion if and only if there exists a
reach-able marking m and transitions t, u, v such that:
1. (i) t, u and v are enabled at m, (ii) •t ∩•u≠∅ ≠ •u ∩•v, (iii) •t ∩•v = ∅ (symmetric case); or
2. (i) t and v are enabled at m, (ii) u is not enabled at m but it becomes enabled after the firing of t, and (iii) •t ∩ •v = ∅ and •v ∩ •u ≠ ∅ (asymmetric case).
In case 1, t and v are concurrently enabled but the firing of one disables an alternative (u) to the other. In case 2, the firing of t enables an al-ternative to u. An example of symmetric confusion is given by m={p1,p7,p2}, t=b, u=c and v=g in Figure 2.1, while for the asymmet-ric case take m={p1, p2}, t=a, v=b and u=c in Figure 2.2
16
Figure 2.1 Petri net with symmetric confusion
Figure 2.2 Petri net with asymmet-ric confusion
17
2 . 3 D E T E R M I N I S T I C N O N S E Q U E N T I A L P R O -C E S S E S
A deterministic nonsequential process (or just process) [7] represents the equivalence class of all firing sequences of a net that only differ in the order in which concurrent firings executed. It is given as a mapping: π: D→N from a deterministic occurrence net D to N (preserving presets and postsets), where a deterministic occurrence net is such that: 1) the flow relation is acyclic,
2) there are no backward conflicts (∀p ∈P.| •p|≤ 1), and 3) there are no forward conflicts (∀p ∈P. |p•|≤ 1).
We let °D = {p| •p=∅} and D°= {p| p•=∅} be the sets of initial and final places of D, respectively (with π(°D) be the initial marking of N). When N is an acyclic safe net, the mapping π: D → N is just an injective graph homomorphism: without loss of generality, we name the nodes in D as their images in N and let π be the identity. The firing sequences of a process D are its maximal firing sequences starting from the mark-ing °D. A process of N is maximal if its firmark-ing sequences are maximal in N.
For example, take the net in Figure 2.2, the equivalence class of the fir-ing sequences m0
a b
→ b and m0 b a
→ is the maximal process D with places {p1, p2} and transitions {a: p1→p3, b: p2 →p4}, where °D = {p1, p2} and D° = {p3, p4}.
Given an acyclic net we let ⪯=F* be the (reflexive) causality relation and say that two transitions t1 and t2 are in immediate conflict, written
t1 #0 t2 if t1 ≠t2 ∧•t1 ⋂ t2• ≠∅.
Moreover, the conflict relation # is defined by letting x # y if there are t1, t2∈T such that (t1, x), (t2, y) ∈ F* and t1#0 t2.
Then, a nondeterministic occurrence net (or just occurrence net is a net O= (P, T, F) such that:
1) the flow relation is acyclic,
2) there are no backward conflicts (∀p ∈ P. |• p| ≤ 1), and 3) there are no self-conflicts (∀t ∈ T. ¬(t#t)).
18
2 . 4 N E T S W I T H P E R S I S T E N C Y
Nets with persistency p-nets [8] partition the set of places into regular places P (ranged by p, q, ...) and persistent places P (ranged by p,q, …). We use s to range over S=P⋃ P and write a p-net as a tuple (S, T, F). Intuitively, persistent places guarantee some sort of monotonicity about the knowledge of the system. Technically, this is realised by let-ting states be bags of places b∈N∞S. Instead of multisets, with the
con-straint that b∈ NS for any regular place p ∈P and b(p) ∈ {0, ∞} for any
persistent place p ∈ P. To guarantee that this property is preserved by firing sequences, we assume that the postset t• of a transition t is the bag such that: t• (p) = 1 if (t, p) ∈ F (as usual); t• (p) = ∞ if (t, p) ∈F; and t• (s) = 0 if (t, s) ∉ F.
We say that a transition t is persistent if it is attached to persistent places only (i.e. if •t⋃t• ⊆P).
The notions of enabling, firing, firing sequence and reachability extend in the obvious way to p-nets (when markings are replaced by bags). For example, a transition t is enabled at the bag b, written b→, if •t ⊆ b, and t the firing of an enabled transitions is written b→ bt ′ with b’=b\•t ⋃ t•. A marked p-net (N, b0) is 1-∞-safe if each reachable bag b ∈ [b0⟩ is such
that b(p) ∈ 2 for all p ∈ P and b(p) ∈ {0, ∞} for all 𝐩 ∈ P. Note that in 1-∞-safe nets the amount of information conveyed by any reachable bag is finite, as each place is associated with one bit of information (marked or unmarked).
Graphically, persistent places are represented by circles with double border.
The notion of confusion extends to p-nets, by checking direct conflicts w.r.t. regular places only.
19
2 . 5 D Y N A M I C N E T S
Dynamic nets [9] are Petri nets whose set of places and transitions may increase dynamically. We focus on a subclass of persistent dynamic nets that only allows for changes in the set of transitions, which is defined as follows.
(Dynamic p-nets). The set DN(S) is the least set satisfying the recursive equation: DN(S)={(𝐓, 𝐛)| 𝐓 ⊆ 𝟐𝐬 × 𝐃𝐍(𝐒) ∧ 𝐓 𝐟𝐢𝐧𝐢𝐭𝐞 ∧
𝐛 ∈ 𝐍∞𝐒}.
The definition above is a domain equation for the set of dynamic p-nets over the set of places S: the set DN(S) is the least fixed point of the equa-tion. The simplest elements in DN(S) are pairs (∅, b) with bag b∈N∞S
(with b(p)∈N for any p∈P and b(p)∈ {0, ∞} for any p ∈P).
Nets (T, b) are defined recursively; indeed, any element t = (S, N) ∈ T stands for a transition with preset S and postset N, which is another el-ement of DN(S). An ordinary transition from b to b' has thus the form (b, (∅, b')). We write S→ N for the transition t= (S, N), •t=S for its preset, and t•= N∈ DN(S) for its postset. For N= (T, b) we say that T is the set of top transitions of N. All the other transitions are called dynamic. The firing rule rewrites a dynamic p-net (T, b) to another one. The firing of a transition t = S→ (T', b') ∈ T consumes the preset S and releases both the transitions T' and the tokens in b'. Formally, if t = S→ (T', b') ∈T with S ⊆ b then (T, b)→ (T ⋃ T', (b\ S) ⋃ b'). t
The notion of 1-∞-safe dynamic p-net is defined analogously to p-nets by considering the bags b of reachable states (T, b).
Figure 2.3 Dynamic p-net
Figure 2.4 The corresponding p-net(⦃N⦄)
20
A sample of a dynamic net is shown in Figure 2.3, whose only dynamic transitions, which is activated by t3, is depicted with dashed border. The arrow between t3 and b denotes the fact that b is activated dynam-ically by the firing of t3: p3̅̅̅̅ → (b: p2 → p4, {p5̅̅̅̅}).
We show that any dynamic p-net can be encoded as a (flat) p-net. Intu-itively, we release any transition t immediately, but we add a persistent place pt to its preset, to enable t dynamically (pt is initially empty if and
only if t is not a top transition). Given a set T of transitions, bT is the bag
such that bT(pt)=∞ if t∈T and bT(s)=0 otherwise.
For N = (T, b) ∈ DN(S), we let T(N) = T ∪ ⋃t∈Tt • be the set of all (pos-sibly nested) transitions appearing in N.
(From dynamic to static). Given N= (T, b) ∈ DN(S), the cor-responding p-net ⦃N⦄ is defined as ⦃N⦄ = (S ⋃ PT(N), T(N), b⋃bT), where:
• PT(N)= {pt | t∈T(N)}; and
• F is such that for any t=S → (T’, b’) ∈T(N) then t: •t⋃{pt}→b’⋃bT’.
The transitions of ⦃N⦄ are those from N (set T(N)). Any place of N is also a place of ⦃N⦄ (set S). In addition, there is one persistent place pt for each
t∈T(N) (set PT(N)). The initial marking of ⦃N⦄ is that of N (i.e. b) together
with the persistent place tokens that enable the top transitions of N (i.e. bT). We safely remove PT⊆PT(N) (and bT) from the flat p-net without any
consequences.
Example 1. The dynamic net net N in Figure 2.3 is encoded as the p-net ⦃N⦄ in Figure 2.4, which has as many transitions as N, but contains an additional persistent place pb that indicates the availability of tran-sition b after firing t3.
21
2 . 6 S T R U C T U R A L B R A N C H I N G C E L L S
A structural branching cell represents a statically determined locus of choice, where the firing of some transitions is considered against all the possible conflicting alternatives. To each transition t we assign an s-cell [t]. This is achieved by taking the equivalence class of t w.r.t. the equiv-alence relation ↔ induced by the least preorder ⊑ that includes imme-diate conflict #0 and causality ⪯.
For convenience, each s-cell [t] also includes the places in the presets of the transitions in [t], i.e., we let the relation Pre-1 be also included in ⊑,
with Pre= F ∩ (P × T). This way, if (p, t) ∈ F then p ⊑ t because p⪯ t and t ⊑ p because (t, p) ∈ Pre−1.
Formally, we let ⊑ be the transitive closure of the relation #0∪ ⪯ ∪ Pre−1. Since #
0 is subsumed by the transitive closure of the relation ⪯
∪ Pre−1, we equivalently set ⊑ = (⪯ ∪ Pre−1)∗. Then, we let ↔=
{(x, y) ∣ x ⊑ y ∧ y ⊑ x}. Intuitively, the choices available in the equiva-lence class [t]↔ of a transition t must be resolved atomically.
(S-cells). Let N= (P, T, F) be a finite, nondeterministic oc-currence net. The set BC(N) of s-cells is the set of equivalence classes of ↔, i.e. BC(N) = {[𝐭]↔ ∣ 𝐭 ∈ 𝐓}.
We let C range over s-cells. By definition it follows that for all C, C’ ∈ BC(N), if C ⋂C’≠∅ then C=C’. For any s-cell C, we denote by NC the
sub-net of N whose elements are in C ∪ ⋃t∈Ct •. Abusing the notation, we denote by °C the set of all the initial places in NC and by C° the set of all
the final places in NC.
(Transactions). Let C∈BC(N). Then a transaction 𝜃 of C, written 𝜃:C, is a maximal (deterministic) process of NC.
Since the set of transitions in a transaction 𝜃 uniquely determines the corresponding process in NC, we write a transaction 𝜃 simply as the set
of its transitions.
Example 2. The net in Figure 2.5 has the three s-cells, whose transac-tions are listed in the right side of the figure.
22
Figure 2.5 Structural branching cells
The following operation ⊖ is instrumental for the encoding and stands for the removal of a minimal place of a net and all the elements that cas-ually depend on it. Formally, 𝑁 ⊖ 𝑝 is the least set that satisfies the rules (where °(_) has higher precedence over set difference):
𝑞 ∈ °𝑁\𝑝 𝑞 ∈ 𝑁 ⊝ 𝑝 𝑡 ∈ 𝑁 • t ⊆ 𝑁 ⊖ 𝑝 𝑡 ∈ 𝑁 ⊖ 𝑝 𝑡 ∈ 𝑁 ⊖ 𝑝 𝑞 ∈ 𝑡 • 𝑞 ∈ 𝑁 ⊖ 𝑝 Example 3. Consider the s-cells in Figure 2.5. The net NC1casually
de-pends on p1. Similarly, NC2 ⊖ p7. The cases for C3 are in Figure 2.6
Figure 2.6 Removing places from s-cell C1: 𝜃a={a} 𝜃d={d} C2: 𝜃f={f} 𝜃e={e} C3: 𝜃bg={b, g} 𝜃c={c} NC3 ⊖ p2 NC3⊖ p3 NC3⊖ p8
23
2 . 7 E N C O D I N G S C E L L S A S C O N F U S I O N -F R E E D Y N A M I C N E T S
Intuitively, the encoding works by explicitly representing the fact that a place will not be marked in a computation. We denote with p̅ the place that model such negative information about the regular place p and let P
̅ = {p̅|p ∈ P}1. The encoding uses negative information to recursively
decompose s-cells under the assumption that some of their minimal places will stay empty.
(From s-cells to dynamic p-nets). Let N=(P,T,F,m) be a marked occurrence net. Its dynamic net [N]∈DN (𝐏 ∪ 𝐏̅) is defined as [N]= (Tpos ⋃ Tneg, m), where:
Tpos = { °C → (∅, θ° ∪ C°\θ°̅̅̅̅̅̅̅) ∣ C ∈ BC(N) and θ: C }
Tneg = { p̅ → (T′, C°\(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅) ∣ C ∈ BC(N) and p ∈ °C and(Tc⊖ p)° ′, b) = [Nc⊖ p]}
For any s-cell C of N and transaction 𝜃:C, the encoding generates a tran-sition t𝜃,C=(°C → (∅, θ° ∪ C°\θ°̅̅̅̅̅̅̅)) ∈Tpos to mimic the atomic execution
of 𝜃. Despite °𝜃 may be strictly included in °C, we set °C as the preset of t𝜃,C to ensure that the execution of 𝜃 only starts when the whole s-cell C
is enabled. Each transition t𝜃,C ∈Tpos, that we call positive transition, is a
transition of an ordinary petri net because its postset consists of (i) the final places of 𝜃 and (ii) the negative versions of the places in C°\𝜃°. A token in 𝑝̅ ∈ C°\θ°̅̅̅̅̅̅̅ represents the fact that the corresponding ordinary place p∈C° will not be marked because it depends on discarded transi-tions (not in 𝜃).
Negative information is propagated by the transitions in Tneg, that we
call negative transitions. For each cell C and place p∈°C, there exists one dynamic transitions tp,C=p̅ → (T′, 𝐶°\(𝑁̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅) whose preset is just p̅ 𝑐⊖ 𝑝)°
and whose postset is defined in terms of the subnet 𝑁𝑐⊖ 𝑝. The postset
of tp,C accounts for two effects of propagation: (i) the generation of the
negative tokens for all maximal places of C that causally depend on p, i.e, for the negative places associated with the ones in C° that are not in (𝑁̅̅̅̅̅̅̅̅̅)°; and (ii) the activation of all transitions T’ obtained by encod-𝑐 ⊖ 𝑝 ing 𝑁𝑐⊖ 𝑝, i.e, the behaviour of the branching cell C after the token in the minimal place p is excluded. We remark that the b in (T’,b)=[𝑁𝑐⊖
𝑝]is always empty, because: i) NC is unmarked and, consequently, 𝑁𝑐⊖
1 The notation 𝑃̅ denotes just a set of places whose names are decorated with a bar; it should not
24
𝑝 is unmarked, and ii) the initial marking of [N] corresponds to the ini-tial marking of N.
Figure 2.7 Encoding of branching cells
Example 4. Consider the net N and its s-cells in Figure 2.5. Then [N]=(T,b) is defined such that b is the initial marking of N, i.e, b={p1,p2,p7}, and T has the transitions shown in Figure 2.7.
First consider the s-cell C1. Tpos contains one transition for each
trans-action in C1, namely ta (for 𝜃a : C1) and td (for 𝜃d : C1). Both ta and td have
°C1={p1} as preset. By definition of Tpos, both transitions have empty
sets of transitions in their postsets. Additionally, ta• produces tokens in
𝜃a°={p3} (positive) and 𝐶̅̅̅̅̅̅̅̅̅̅ = {𝑝3, 𝑝6}\{𝑝3}1°\𝜃𝑎° ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = {𝑝6}̅̅̅̅̅̅ (negative),
while td• produces tokens in 𝜃d°={p6} and 𝐶̅̅̅̅̅̅̅̅̅̅ = {𝑝31°\𝜃𝑑° ̅̅̅̅}. Finally,
t1∈Tneg propagates negative tokens for the unique places in °C1={p1}.
Since 𝑁𝑐1 ⊖ p1 = (∅ , ∅). Hence t1 produces negative token for all
max-imal places of C1, i.e. {𝑝3̅̅̅̅, 𝑝6̅̅̅̅}. For the s-cell C2 we analogously obtain
the transitions te, tf and t7.
The S-Cell C3 has two transactions 𝜃bg and 𝜃c. Hence, [N] has two
transi-tions tbg, tc ∈ Tpos. Despite 𝜃bg mimics the firing of b and g, which are
dis-connected from the place p3, it is included in the preset of tbg to
post-pone the firing of tbg until C1 is executed. Transitions t2, t3, t8 ∈Tneg
prop-agate the negative information for the places in °C3= {p2,p3,p8}. The
transition t3 has •t3= {𝑝3̅̅̅̅} as its preset and its postset is obtained from
𝑁𝑐3⊖ p3, which has two (sub) s-cells Cb and Cg (see Figure 2.6). The
transition tb and t2’ arise from Cb, and tg and t8’ from Cg. Hence
t3•=({tb,t2’,tg,t8’},{𝑝5̅̅̅̅}) because [𝑁𝑐3 ⊖ p3]=({tb,t2’,tg,t8’},∅) and ta: p1→(∅,{p3, p6̅̅̅̅}) for 𝜃a td: p1→(∅,{p6, p3̅̅̅̅}) for 𝜃d t1: p1̅̅̅̅→(∅,{ p3̅̅̅̅, p6̅̅̅̅}) te: p7→(∅,{p8, p9̅̅̅̅}) for 𝜃e tf: p7→(∅,{p9, p8̅̅̅̅}) for 𝜃f t7: p7̅̅̅̅→(∅,{p8̅̅̅̅, p9̅̅̅̅}) tbg: p2,p3,p8→(∅,{p4,p10, p5̅̅̅̅}) for 𝜃bg tc: p2,p3,p8→(∅,{p5, p10̅̅̅̅̅, p4̅̅̅̅}) for 𝜃c t2: p2̅̅̅̅→({tg,t8’},{ p4̅̅̅̅, p5̅̅̅̅ }}) t3: p3̅̅̅̅→({ tb,t2’,tg,t8’},{p5̅̅̅̅}) t8: p8̅̅̅̅→({tb,t2’}, p5̅̅̅̅, p10̅̅̅̅̅}) where: tb: p2→(∅,{p4}) t2’: p2̅̅̅̅→(∅,{p4̅̅̅̅}) tg: p8→(∅ ,{p10}) t8’: p8̅̅̅̅ → (∅, {p10̅̅̅̅̅} )
25 C3°\(NC3 ⊖ p3)°
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = p5̅̅̅̅. Similarly, we derive t2 from (NC3 ⊖ p2) and t8
from NC3⊖ p8.
The flattening of [N] in the Example 4 to the corresponding p-net ⦃N⦄ is shown in Figure 5.4 and Figure 5.5. In these figures the negative places p1
̅̅̅̅, p2̅̅̅̅ and p7̅̅̅̅ are not generated, since we suppose that the places p1, p2 and p7 are initially marked.
26
2 . 8 T E C H N O L O G I E S
JAVA LANGUAGE
The programming language we choose for implementing the tool is the well-known called Java language [10, 11]. The main features of Java are listed below.
Types safety: Java is designed to enforce type safety. Anything in Java happens inside an object and each object is an instance of a class; Portability: a compiled Java program can be run in any Java virtual ma-chine installed systems;
Design benefits: Large programs are very difficult to write. OOP (Object Oriented Programming) forces designers to go through an extensive planning phase, which makes for better design with fewer flaws; Effective Problem solving: OOP is the most suitable paradigm to handle the faced complex problem since allows us to break down the problem into bit-sized problems that you can solve one object a time.
Code reusability: thinking about future developments;
Available libraries: There are many available Java libraries used to im-plement some parts of the tool. As we will see, in our case, we use a library called SAX API (Simple API for XML) [12] for parsing the PNML file.
PNML FORMAT
PNML (Petri Net Model Language) [13] is an XML-based syntax de-signed as a standard interchange format for Petri nets and defined by standard ISO/IEC 15909. A report on PNML as defined by standard ISO is available [14].
PNML, being XML-based, define each object through XML tags. The outermost tag is <pnml>, it defines that the document is about pnml definitions. Going more inside, we find the <net> tag first, it means that a Petri net definition starts from that point. The most internal tags
27
define the objects of Petri nets. Among objects described by PNML we are interested in the following ones:
• places represented with <place> tags
• transition represented with <transition> tags • arcs represented with <arc> tags
COMMON INFORMATION ABOUT NET OBJECTS
Each net node (places, transitions) has the following information: • unique identifier(id): a string that identifies uniquely each node
in-side the net, it is defined through id attribute of object tag;
• name: the label of the node in the graphical representation, it is de-fined through tag <name> inside the tag object
• bidimensional coordinate and dimension: relative to the graphical representation, they are defined through the <graphics> tag. Within such tag, <position> defines the horizontal and vertical co-ordinate respectively through its attributes x and y; while <dimen-sion> defines the width and the height respectively through its at-tributes x and y.
SPECIFIC INFORMATION ABOUT A NET OBJECT TYPE
Every object, according to its kind (place, transition, arc) has additional specific information. Among these kinds of information, we will see only those that interest us for our purpose.
The only one associated to each place is initial marking: it states the number of tokens the place has, and it is defined through the <initialMarking> tag
Those related to each arc are:
• source: the identifier(id) of the source node (place or transition) • target: the identifier(id) of the target node (place or transition) • probability: the probability of source node to choose the arc among
28 EXAMPLE
Code 2.1 Petri net definition in PNML language.
The URL contained in the type attribute of the <net> tag is a reference to grammar for the definition of Petri nets composed by transitions and places
Figure 2.8 is a graphical representation of Petri net in Code 2.1 given by a PNML handler tool called Woped [15]. This tool lets us, in addition to show graphically the net, to explore its semantics by simulating a set of firing sequences.
Figure 2.8 Petri net in Woped
<pnml><net type="http://www.informatik.hu-ber-lin.de/top/pntd/ptNetb" id="noID"> <transition id="c0"> <name><text>t1</text></name> <graphics> <position x="50" y="10"/> <dimension x="40" y="40"/> </graphics> </transition> <place id="c1"> <name><text>p1</text></name> <graphics> <position x="50" y="100"/> <dimension x="40" y="40"/> </graphics> <initialMarking><text>1</text></initialMarking> </place>
<arc id="0" source="c1" target="c0"></arc> </net></pnml>
29
The input PNs that will be processed by our tool, are designed by using Woped.
DOT FORMAT
DOT is a graph description language [16] used by the Graphviz [17] . It allows the definition of any graph in a simple and intuitive way through its syntax and relative semantic.
The language describes three main kinds of object: graphs or sub-graphs, nodes and edges. The main outermost graph can be direct or indirect.
Each object can have an associated list of attributes. Each of these is a pair of strings of type: att_id = att_value ; where att_id is a string that identifies the attribute, and att_value is a string corresponding to attrib-ute value. A list of attribattrib-utes is enclosed by square brackets and follows the definition of an object to which it is associated.
Code 2.2 Graph definition in DOT language.
A directed Graph identified by G is defined through digraph keyword. The
definitions of nodes, edges and subgraph of the main graph G are inside the area next to it delimited by curly brackets.
digraph G { graph [labelloc=top,label="paper",fontname="Verdana",font-size=12]; edge [fontname="Verdana",fontsize=9]; node [fontname="Verdana",fontsize=9,shape=circle]; c0 [label="p1",pos="20,240"]; c1 [label="p2",shape="doublecircle",pos="75,240"]; c2 [label="t1",shape="box" pos="50,150"]; subgraph F{ c3 [label="p3", pos="50,100"];
c4 [label="t2", shape="box", pos="50,20"]; }
{c0,c1}->{c2}; {c2}->{c3}; {c3}->{c4}; }
30
As we see in Code 2.2, each kind of object has an associated label that will be shown next to it in graphical visualization.
The following attributes define the value and the type of label text • fontname: define the font for the label text
• fontsize: define the size of characters • label: define the label text
• labelloc: define the position of the label respect to the associated object
In any node, instead, the “pos” attribute indicates its bidimensional co-ordinate in graphical space, while attribute “shape” indicates its shape. The list of attributes next to graph keyword define the label attributes of the graph (graph have as label text “paper” and is shown at the top of the graph).
The list of attributes immediately after the keywords node and edge de-fine respectively the default attributes of homonymous types of object. The pair shape=circle means that any node with no specified shape will appear as a circle by default.
Figure 2.9 is the graphical interpretation of Code 2.2 given by Graphviz tool
Figure 2.9 Drawing of graph written in DOT
All the nodes are represented with a circle except for p2 (double circle) and for t1 and t2 (boxes).
In DOT files outputted by our tool we use this convention: places are represented through circles, persistent places are represented through double circles, transitions are represented through boxes.
31
3 REQUIREMENTS AND SOFTWARE ARCHITECTURE
In section 3.1 we discuss the requirements analysis of our project, that is, the specification our tool must comply with.
Later, in section 3.2, we will show the architecture of our tool by listing the various Java packages that make up it and by describing how they interact with each other.
32
3 . 1 R E Q U I R E M E N T A N A L Y S I S
The work our tool has to do can be split in the following phases: 1. read the petri net given as input;
2. represent the petri net through suitable data structures; 3. check if the petri net satisfies the desired requirements;
4. decompose the petri net into s-cells and compute, for each s-cell, its maximal transactions;
5. encode the petri net into a dynamic net in a compositional way; 6. transform the dynamic net into a flat net, by adding additional
persistent places;
7. output the corresponding confusion-free net.
In the next paragraphs, we see these macro phases in more detail.
READING THE PETRI NET GIVEN AS INPUT
Our tool has to read a PNML file describing a petri net and continue with the processing if the net satisfies the requirements.
First, we need to parse a PNML file to retrieve information about nodes and arcs. Then we need to represent the Petri net through data struc-tures to manipulate it.
REPRESENTING A PETRI NET THROUGH SUITABLE DATA STRUC-TURES
A petri net is represented in the form of two unary relations T and P that correspond to the set of transitions and places, respectively, and a bi-nary relation F corresponding to the adjacency matrix2 (the set of arcs).
In addition, other relations are computed that will be useful for the next phases. Such relations, as already mentioned in section 2.3, are the fol-lowing:
• causality (⪯), with ⪯ = F*;
2 Square matrix used to represent a finite graph. The cells of the matrix indicate whether pairs
33
• presets of each place (Pre), with Pre = (P×T) ⋂F; • immediate conflict (#0), with #0= (Pre-1 ⋅ Pre) ⋂(¬I);
• conflict (#), with #= (⪯-1⋅#0⋅⪯) ⋃#0;
Once all these relations are represented though Java data structures, they can be processed by our tool.
CHECKING IF THE PETRI NET SATISFIES THE DESIRED REQUIRE-MENTS
According to [2], the Petri net given as input must satisfy the following: − it must be acyclic: there are no cycles in the net;
− every place has at most one incoming arc and every transition must have at least one incoming arc;
− no self-conflict transitions.
Figure 3.1 self-conflict
t conflicts with itself, by conflict inheritance between t2 and t1.
The net in Figure 3.1 contains a self-conflicting transition t. t is causally related to both t2 and t1, these last two are, in turn, in conflict. Then it cannot be possible that tokens are in both p1 and p2, at the same time. This means that t can never be enabled.
Our tool can proceed with the computation if the net fulfils the above requirements. For example, the nets in Figure 2.1 and Figure 2.2 respect the requirements.
34
DECOMPOSING THE PETRI NET INTO S-CELLS
By definition of s-cells, we know that each place and transition belongs exactly to one cell. The procedure for computing the set BC(N) of s-cells is the following:
1. take a transition t;
2. create an s-cell C whose elements are contained in [𝑡]↔
3. compute the set of maximal transactions of C 4. set 𝐵𝐶(𝑁) ∶= 𝐵𝐶(𝑁) ∪ 𝐶
5. repeat 1 until all transitions belong to some S-cell.
ENCODING THE PETRI NET INTO A DYNAMIC PETRI NET
The encoding of a Petri net into a dynamic Petri net is done in a compo-sitional way.
For each s-cell C, encode it into a dynamic net and, recursively, encode the s-cells generated by considering the disappearance of alternatives from C. Finally, compose and connect the encoded dynamic nets to-gether.
For each s-cell C, its encoding is given by the union of the positive dy-namic transition Tpos and the negative dynamic transition Tneg.
As seen in Chapter 2,Each maximal transaction ϴ of C is associated with a positive dynamic transition of the form °C → (∅, θ° ∪ C°\θ°̅̅̅̅̅̅̅).
Therefore, to represent a positive dynamic transition we need a data structure that is able to store and represent:
• its associated transaction θ;
• the set of places that make up its preset: °C;
• the set of places that make up the positive part of its postset: θ°; • the set of persistent places that make up the negative part of its
postset: C° ∪ θ°̅̅̅̅̅̅̅̅̅.
Each place p belonging to the preset of C is associated with a negative dynamic transition of the form p̅ → (T′, C°\(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅) c⊖ p)°
Therefore, to represent a negative dynamic transition, we need a data structure that is able to store and represent:
• the persistent place belonging to its preset: p̅;
• the set of persistent places that constitute its post-set: C°\(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ c⊖ p)°
35
• the dynamic net T′ released by the firing
The dynamic net T′is computed from the net N
c⊖ p obtained from the
s-cell C by erasing all nodes that are permanently disabled because of their causal dependence from p which is supposed to be never marked (because p̅ is marked).
In the end all the dynamic nets derived by the encoding of all s-cells that compose the original Petri net are merged together to form the final dy-namic petri net.
During the encoding, it may happen that the same s-cell is computed multiple times by decomposing different petri nets. A collection of s-cells allows to avoid this waste of computation by keeping track of al-ready computed s-cells.
Figure 3.2 Two different petri nets producing the same s-cell C1
The same applies to dynamic nets: two Petri nets with the same set of transitions and post places produce the same dynamic nets, but they can be computed at different points of the program by erasing different places with their descendants from the same Petri net.
Figure 3.3 Two Petri nets with the same set of transitions.
The Petri nets obtained by removing p2 and p3 have the same set of transi-tions{b}. The removed nodes have the dotted outline.
36
FLATTENING DYNAMIC NETS, BY ADDING PERSISTENT PLACES
We need to flatten each dynamic net to obtain a final p-net. Flattening a dynamic net amounts to take the results of the flattening of its dynamic transitions and combine them.
Let C be an s-cell, and θ: C be one of its maximal transactions. The flat-tening of a positive dynamic transition °C → (∅, θ° ∪ C°\θ°̅̅̅̅̅̅̅) generates a new transition t labelled with the associated transaction θ, then to create arcs going from places in °C to t and others that go from t to places in θ° and to persistent places in C°\θ°̅̅̅̅̅̅̅. Finally, a persistent place pt added to the preset of t. This will be useful to represent the activation
of t.
Figure 3.4 flattening of a positive transition t where θ = 𝑡1, 𝑡2 .
The flattening of a negative dynamic transition p̅ → (T′, C°\(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅) c⊖ p)° is done via a depth first traversal algorithm. Since each negative transi-tion generates a dynamic net T′, the algorithm first performs the
flat-tening of T’, then generates an auxiliary transition t and as well as: • an arc going from persistent place p̅ to t
• arcs going from t to persistent places in C°\(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅. c⊖ p)°
• for each dynamic transition g of dynamic net T′, arcs going from t
to persistent places pg that represents the activation of g in the
p-net.
As in the positive case, a persistent place pt is added to the preset of t.
A token in pt represents the activation of t.
37
Figure 3.5 flattening of negative transition t
where (C°/(N̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ = (p4)c⊖ p)°) ̅̅̅̅̅̅, while pf and pg represent the activation of transitions f and g, respectively, which belong to T’
OUTPUTTING THE CORRESPONDING CONFUSION FREE-NET
Our tool has to output the resulting p-net into two format files: DOT and PNML. The first is mainly used for graphical visualization of the Petri net, while the latter is used for its semantic interpretation. First, the DOT file is generated, which is then compiled by the Graphviz tool and transformed to an image file (png or svg formats).
The semantic interpretation of a PNML file is performed by the Woped tool. This process consists of showing graphically all the possible firing sequences of transitions, so the absence of confusion.
Unfortunately, the graphical visualization that supports semantic inter-pretation doesn’t place nodes automatically for a correct visualization, but it simply places them in their respective coordinates, as specified in the PNML file.
Graphviz is helpful, because this tool can generate another DOT file with the addition of bidimensional coordinates for each node for an ordered layout.
Therefore, before generating the PNML file, our tool reads this last DOT file to retrieve the right coordinates for each node. The right association from nodes specified in the DOT file and those specified in the PNML file is done thanks to their identifier strings.
Persistent places have to represented in an appropriate way:
• PNML: this format, when interpreted by Woped, doesn’t allow to define a persistent place or a transition. To account for this,
38
we associate each arc going from a persistent place to a transi-tion with a symmetrical arc going in the opposite directransi-tion. This way, the place remains marked at each firing. In addition, the persistent place and the persistent transition have a different size to distinguish it from other places and transitions
• DOT: this format allows to define different shapes for each node, so we simply associate a double circle shape to persistent places.
39
3 . 2 A R C H I T E C T U R E
In this section, we see how the various phases are implemented by ded-icated packages and how they interact with each other.
READING PETRI NET GIVEN AS INPUT
The parser of PNML files is implemented in the parser package. The parser uses the representation package to represent net nodes re-trieved from PNML file as Java data structures to be processed by our tool. In fact, it provides classes to:
• represent each net node (place or transition) as a Java Object by storing in it information about the node retrieved from PNML file such as its identifier code, its label name, its kind (place or transition) and, if it is a place, how many tokens it has initially; • store each of these objects in an array (which we call
transla-tor), so that from now on, in order to refer to a certain node, we only need an integer that corresponds to its position in the array. The following is a simple example of how a Petri net is represented through Java data structures:
Figure 3.6 Petri net representation
The table on the right is the translator array. Translator contains in the first position a Java object representing the place “p”, and in the next positions Java objects representing transitions t1 and t2. From now on, p will be identi-fied with 0, while t1 and t2 will be identiidenti-fied with 1 and 2, respectively.
REPRESENTING PETRI NETS THROUGH DATA STRUCTURES
Once all net nodes can be identified through an integer (its position in translator), petrinet package deals with Petri net representation. A Petri net representation consists of:
0 place
name p token 1 1 transition name t1 2 transition name t2
40
• a unary relation P that keeps track of which integers identify a place, where i ∈ P means that node identified with i is a place; • a unary relation T that keeps track of which integers identify a
transition, where i ∈ T means that node identified with i is a transition;
• a binary relation F that keeps tracks of the arcs of the net where (𝑖, 𝑗) ∈ 𝐹 means that there is an arc from the node identified with i to the node identified with j.
Going in more detail, the unary relations P and T are represented through bit vectors: a value of 1 in the i-th position of vector means that the node identified with i belongs to the relation.
While the binary relation F is represented through a matrix of bit: value of 1 in the i-th row and j-th column means that (i,j) ∈ F.
The following are examples of relations P, T and F of the Petri net de-scribed in the example of Figure 3.6
Figure 3.7 Petri net representation with unary and binary relations.
In P, the value of 1 in the first position indicates that the node identified with 0 is a place (p is identified with 0).
In F, the value of 1 in position (0,1) represents the arc from p (identified with 0) to t1 (identified with 1), while the value of 1 in position (0,2) represents the arc from p to t2 (identified with 2).
The bitstructures package contains classes for the definition of bit vectors and bit matrices and the operations between them.
DECOMPOSING PETRI NET IN S-CELLS
This step is done entirely by the package petrinet that contains also classes and methods to:
• decompose Petri net into s-cells; • represent s-cells;
• represent and compute maximal transactions of each s-cell; P 1 0 0 0 1 2
0 1 2 0 0 1 1 T 0 1 1 F 1 0 0 0 0 1 2 2 0 0 0
41
• implement the ⊖ operator: producing a Petri net by removing places and its descendants.
ENCODING S-CELLS INTO DYNAMIC NETS
A Petri net is encoded into a dynamic net by merging all the dynamic nets obtained by encoding its s-cells.
The method that implements the encoding of Petri nets and s-cells into dynamic nets is included in the petrinet package.
The dynamic_petrinet package contains also classes to represent dynamic nets and dynamic transitions, both positive and negative ones. FLATTENING DYNAMIC NETS, BY ADDING PERSISTENT PLACES The method that implements the flattening of the dynamic net into final p-net is contained into dynamic_petrinet package.
In the changeover from dynamic to the p-net, additional net nodes are added while others are imported from the original net.
The persistent_net package supports the flattening and contains also classes for the representation of p-nets.
OUTPUTTING THE CORRESPONDING CONFUSION-FREE NET
The output package mainly deals with outputting the resulting p-net into DOT and PNML files.
As we have already mentioned before, first the DOT file is produced. Subsequently, Graphviz is called to process such DOT file and to pro-duce a target DOT file in which the coordinates of each node are speci-fied.
Our tool extrapolates the coordinates from this last DOT file and assigns each of them to the corresponding node.
Finally, the output package allows one to the final p-net into a PNML file by specifying the coordinates of each node.
42 4 IMPLEMENTATION
In this chapter we will focus on the implementation part of our tool. In section 4.1 we will list the main implemented algorithms.
In section 4.2 we will describe the Java packages by using class dia-grams. A class diagram of a package graphically describes the relation-ships that occur between classes that make up the package. In addition, for each class, we will show its main attributes and methods.
43
4 . 1 I M P L E M E N T E D A L G O R I T H M S
In this section we will show some of the main algorithms implemented in the tool.
Some of them are already known, while others have been designed ad-hoc for our tool.
We will show the code of each algorithm and, in some cases, the algo-rithm will be described in more detail and some running examples will be shown.
UPPER TRIANGULAR REDUCTION
Graphs are internally represented with adjacency matrices of bits, where indexes of rows/columns are the integers identifiers of the net nodes.
The adjacency matrix describing the input graph may be sparse3, hence
we implement a compression algorithm to save memory space.
Since the net is acyclic, we consider the order between nodes induced by arcs, that is: ∃arc from a to b ⟹ a < b.
We can note that this arrangement induces a partial order between nodes and, consequently, if we assign integer identifiers according to the schema of this arrangement, we can consider the adjacency matrix as an upper triangular one, saving memory space.
In fact, if integer identifiers are assigned according to this schema, we know from the equation above that 𝑎 ≥ 𝑏 ⟹ ∄ 𝑎𝑟𝑐 𝑓𝑟𝑜𝑚 𝑎 𝑡𝑜 𝑏, then all the cells of adjacency matrix under the diagonal must be set to 0. Assigning integer identifiers to each node according to this arrange-ment schema is done by the algorithm described in Code 4.1. The algo-rithm associates each node with a counter called arcs that initially con-tains the number of incoming arcs of the associated node. During the execution of the algorithm, the counter will be decreased after a visit from an adjacent node. An integer identifier will be assigned to a node as soon as its arcs counter will reach 0.
44
In the following code, given a node n, we refer to its identifier as n.id, while we refer to its arcs counter as n.arcs
Code 4.1 Assigning identifier for upper triangular reduction
Given a node n, we refer to its identifier and to its arcs counter with n.id and
n.arcs, respectively.
For example, suppose that we want to assign identifiers to the nodes of the following graph G:
Figure 4.1 Acyclic graph G
The number next to a node represents its arcs counter. Initially, every
coun-ter contains the number of incoming arcs of the associated node.
Initially, we have a source node a, then we can assign the first integer 0 to its identifier (a.id=0) and visit it.
Now we have the following situation described in Figure 4.2. Input: acyclic graph G
Output: integer identifiers of each node belongs to G Set counter ← 0
∀node n ∈ G. Set n.arcs (0) ← number of incoming arcs of n
Set source_nodes(0) ←⦰
Set k ←0
1. Set k ←k+1
2. Set source nodes (k) ← {n ∈G |n.arcs(k-1) =0}
3. If source_nodes(k)=source_nodes(k-1)
a. return
4. For each node n ∈ source_nodes(k)
a. Set n.id ← counter b. Set counter ←counter+1
5. For each unvisited node n∈ source_nodes(k), visit n:
a. ∀p∈ adjacent nodes of n. Set n.arcs(k) ←n.arcs(k-1)-1
45
Figure 4.2 first screenshot of the execution of the algorithm on the graph G
The node a is assigned with 0 as its identifier, while the arcs counter of node
b is set to 0 since it has been decreased from the visit on node a. Coloured nodes are the source nodes: black nodes have already been visited while grey ones are still to be visited and an integer identifier must still be assigned to them.
We proceed with assigning the next integer to the identifier of b (b.id=1) and the subsequent visit to b, then we decrease the arcs coun-ters of c and d by resetting them, and so on. After visiting in sequence the nodes c, d and e, we have the following situation:
Figure 4.3 second screenshot of the execution of the algorithm on graph G f has to be visited and its identifier must still be assigned. We note that the
arcs counter of g has been decreased by 1 from the visit on c.
In the end, we assign an identifier to f (f.id=5) before visiting it. The latter causes the reset of arcs counter of g and, finally, the last integer is assigned to the identifier of g (g.id=6). Finally, all the integer identifiers are assigned to each node according to the desired arrangement schema, as the following figure shows:
Figure 4.4 Termination of the algorithm on graph G All the integer identifiers are assigned to each node
46
SCALAR PRODUCT BETWEEN A MATRIX AND A VECTOR
To compute the product of a matrix A and a vector B we use an itera-tive algorithm: for each row of the matrix, we count in how many posi-tions both the vector B and the row have 1.
Code 4.2 Computing the scalar product between a matrix and a vector
This algorithm takes time Θ(nm) where n and m are respectively the numbers of rows and columns of the matrix.
PRODUCT BETWEEN TWO MATRICES
The product of two matrices is the representation of the set of paths reachable by crossing an arc described by the left operand matrix and subsequently an arc described by the right operand.
We use an iterative algorithm: If there is an arc from i to j in the left operand matrix, then for each arc from j to k, the resulting product ma-trix contains a path from i to k.
Input: matrices A, vector B Output: vector C
For i from 1 to nrows(A): Let sum = 0
For k from 1 to size(B): If Aik Bk
then Set sum ← sum + 1 end if
end for Set Ci ← sum end for
47
Code 4.3: Computing the product between two matrices
The computational complexity of the algorithm is Θ(nmk) where n and m are respectively the numbers of rows and columns of the left operand matrix, while k is the number of columns of the right operand matrix.
TRANSITIVE CLOSURE OF A GENERAL MATRIX
The transitive closure of a bit matrix A is defined as 𝐴+∶= ⋃∞ {𝐴𝑘}
𝑘=1 =
𝐴1∪ 𝐴2 ∪ . .. ∪ 𝐴∞.
There are several algorithms to implement this kind of operation, a sim-ple one can be the following:
Code 4.4 Inefficient computation of the transitive closure of a general matrix.
This simple approach is computationally expensive: let t be the number of steps the iteration requires, the algorithm costs Θ(t) multiplied by the cost of the matrix product (since Ak=A⋅Ak-1). Moreover, at each k-th
Input: matrices A and B Output: matrix C
For i from 1 to nrows(A): For j from 1 to ncolumns(A):
If Aij
For k from 1 to ncolumns(B) Set Cik ← Bjk end for end if end for end for return C Input: matrix A
Output: transitive closure of A (A+)
Set A+←⦰ Set k←1 While Ak ⊈ A+ Set A+ ← A+⋃Ak Set k ← k+1 end while return A+
48
step of the computation, we need to keep two additional matrices in memory: one for the partial result (⋃𝑘−1{𝐴𝑖}
𝑖=1 ) and another one for Ak.
The algorithm that we implement is more efficient, and it doesn’t re-quire a partial result matrix. It is an instance of the already known War-shall Algorithm described in [18]. It is based on the following observa-tion: any path from a node to another node goes through a subset of the nodes of the graph.
The following is the pseudocode of the algorithm:
Code 4.5:Efficient computation of the transitive closure of a general matrix
The computational complexity of the algorithm is Θ(n2m) where n and
m are respectively the numbers of rows and columns of the matrix
TRANSITIVE CLOSURE OF A SYMMETRIC MATRIX
Symmetric adjacency matrices represent undirected graphs since also inverting rows with columns in symmetric matrix results in the same exact matrix.
From that, we can deduce that the transitive closure of a symmetric ma-trix represents a set of disjoint maximal cliques. A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; a maximal clique is a clique that cannot be ex-tended by including one more adjacent vertex. In this case, the maximal cliques are disjoint: a node and its adjacent nodes identify uniquely a maximal clique.
Let A be a symmetric adjacency matrix: we can prove that its transitive closure A+ represents a set of maximal cliques since every two distinct
Input: matrices A Output: matrix C Set C ←A
For k from 1 to nrows(A): For j from 1 to ncolumns(A):
For i from 1 to nrows(A) Set Cij ← Cij ∨ (Cik ∧ Ckj) end for
end if end for end for return C
