Petri Nets: Properties, Analysis and Applications

Petri Nets: an Overview

1. SRGE 2018 1 Petri Nets: Properties, Analysis and Applications Presented By Dr. Mohamed Torky PHD in Computer Science (2018), Faculty of Science, Menoufyia University, Egypt. Member in Scientific Research Group in Egypt (SRGE)

2. Agenda 2

3. Agenda 3

4. 8/12/2018 1- What is Petri Nets ?

5. 8/12/2018 1- What is Petri Nets ? (Transition, Enabling, and Firing Rules) P1 P2 P3 t1 2 3    

6. 1- What is Petri Nets ? (Petri Net Structure) t1 t2 t3 t1 t2 t3 t4 t5 (A sequence Structure) (Concurrent Structure)

7. 1- What is Petri Nets ? (Petri Net Structure) (Synchronization Structure) t1

8. 1- What is Petri Nets ? (Petri Net Structure) (Synchronization and Concurrency Structure) t1

9. 1- What is Petri Nets ? (Example: computation of X=( a+b )/(a-b ) t6 t2 t3 t4 t5 t1 t7 P2 P1 P3 P4 P5 P6 P7 P8 P9 Add Subtract If (a-b≠0) If (a-b=0) Divide X=( a+b )/(a-b)=3 a=8 a=8 b=4 b=4 a+b =12 a-b=4 X=Undefined a-b=4

10. 1- What is Petri Nets ? (Petri Net Properties ) Petri Net Properties Structure Properties Behavior Properties

11. 1- What is Petri Nets ? (Behavior Properties) Behavioral properties of a Petri net depend on the initial marking and the firing policy , so it sometimes called Marking-dependent properties. These properties are thus of great importance when designing dynamic systems , hence, it depends on the behavior of the system not its structure.

12. 1- What is Petri Nets ? (Behavior Properties) Reachability: A Marking is said to Reachable from the initial marking if there exists a firing sequence that transform to (i.e. )   Reachability Graph

13. 1- What is Petri Nets ? (Behavior Properties) Boundness: A Petri net is said to be K-bounded if the number of tokens in each place doesn't exceed a finite number K for any marking reachable from (i.e. )      

14. 1- What is Petri Nets ? (Behavior Properties) Reversibility : A Petri net is said to be reversible if for each marking ), is Reachable From M . A marking M” is said to be a Home State if for each marking ) , M” is Reachable from M   Reachability Graph Reversible Net

15. 1- What is Petri Nets ? (Behavior Properties) Presistence : A Petri net is said to be persistent if, for any two enabled transitions, occurrence of one transition will not disable another. Persistent Net

16. 1- What is Petri Nets ? (Behavior Properties) Fairness : A Petri net is said to be net if, every pair of transitions in the net are in a B-fair relation. i.e. every transition in the net appear infinitely in a finite sequence of transitions   B-Fair Net

17. 1- What is Petri Nets ? (Structure Properties) Structure properties of depend only on its structure, and not on the initial marking and the firing policy. These properties are thus of great importance when designing static systems , since they depend only on the layout, and not on the way the system will be behave, Most of the structural properties can be easily verified by means of algebraic techniques.

18. Agenda 18

19. 2- Analysis Methods of Petri Nets

20. 2-1. Reachability Tree Reachability Tree Example 1: Finite Rechability Tree

21. 2-1. Reachability Tree Reachability Tree Example 2: Infinite Rechability Tree t2 t4

22. 2-2. Incidence Matrix Incidence Matrix : for a Petri Net with n Transitions and m Places , the Incidence Matrix is matrix of integers as:   Where,

23. 2-2. Incidence Matrix For The marking states which result from transitions firing can be Expressed in the following Equation which called State Equation: Where, Such that M is the marking state and A is the incidence Matrix, and u is firing sequence vector (u1, u2, u3,…..)

24. 2-2. Incidence Matrix The Necessary Reachability Condition: Suppose that the destination marking state is is reachable from through the firing sequence . The State equation can be rewritten as:  

25. 2-2. Incidence Matrix Example (1) : given the following such that Does the marking State is reachable from ???   The Incidence Matrix Solution:

26. 2-2. Incidence Matrix Example (2) : ?

27. 3. Reduction Rules

28. 3. Reduction Rules Example : (A) (B) (C) (B) (C) Example :

29. Ordinary PN Subclasses (B) (C)

30. Agenda 30

31. 3.1. High Level Petri Nets (HLPN) (B) (C)

32. 3.1. High Level Petri Nets (HLPN) (Enabling, Firing Rule) (B) (C) t1 can be enabled in the following Modes (1,3), (1,4), (1,5), (1,7), (3,4), (3,5), (3,7) (x , y)

33. 3.1. High Level Petri Nets (HLPN) (Enabling, Firing Rule) (B) (C) Firing modes of t1:         Mode 1: 1 ’(3,5)

34. 3.1. High Level Petri Nets (HLPN) (Enabling, Firing Rule) (B) (C) Firing modes of t1:         Mode 2: 1 ’(1,3)+ 2 ’(3,5)

35. 3.2. Colored Petri Nets (B) (C) Definition A net is a tuple where :  

36. 3.2. Colored Petri Nets (B) (C) P1 P2 P3 t1     1 ,8+ 1 ’ 3 INTEGER INTEGER FlOAT 1 ,5     1 ’3.2 Example : x:INTEGER y:INTEGER p1, p2 INTEGER p3 FLOAT  

37. 3.3. Timing Petri Nets (B) (C) Definition A net is a tuple where : the set of output places to each transition : D:T TS is the a function that define the firing delay of each transition  

38. 3.3. Timing Petri Nets (Enabling, Firing Rule) (B) (C) P1 P2 P3 [1] {4}   1 3 1 5 5     1 3 2 4 5

39. 3.3. Timing Petri Nets (Enabling, Firing Rule) (B) (C) Tasks [0,5 ] {5} Busy 1 Free 1 Free 2 Busy 2 Output Start 1 Finish 1 Start 2 Finish 2 1 [1] {5} [5] {0} [6] {0} 5 6 5 5 6 6 Example: 2 1 3 4 5 6 TIME

40. Agenda 40

41. 4.Petri Nets Applications 41 Petri Net Applications

42. 4.1. Rumors Detection and Blocking in OSNs 42 Colored PN Model for Detecting and Blocking Rumors in OSNs

43. 4.1. Rumors Detection and Blocking in OSNs 43 Tweets URL 7X 4Y 3Z 4Y 3Z 1R 3S 2P 1Q 1R 3S 2P 1Q 1R+2P 3S+1Q 3S+1Q 1R+2P 1R+2P Remove M4 = (7,0,0,0,0,0,0,3,0,0) M1 = (0,4,3,0,0,0,0,0,0,0) M2 = (0,0,0,1,3,2,1,0,0,0) M3 = (0,0,0,0,0,0,0,3,4,0) M0 = (7,0,0,0,0,0,0,0,0,0) M5 = (0,0,0,0,0,0,0,0,0,3) Classify Cred_Ev Detect Block/ Propagate No_URL Cred_URL Cred_No_URL InCred_No_URL InCred_URL Rumor Tweets Good Tweets Good Tweets

44. 4.2. Reachability Analysis 44

45. 4.2. Reachability Analysis 45 8/12/2018 Theorem Given a Colored Petri Net model ) with an initial marking With knowing the variables such that, , , , then the following points can be proved: , such that , such that , such that   where , is the number of all input tokens in Place , is the number of all tokens forward to the Place and is the number of all tokens forward to Place . is the number of tokens forward to Place . is the number of tokens forward to Place is the number of tokens forward to Place , and is the number of tokens forward to Place .  

46. Agenda 46

47. 5. Orbital Petri Nets: A Promising Approach 47 8/12/2018

48. 5 . Orbital Petri Nets: A Promising Approach 48 8/12/2018 : , and V is orbital attribute value (optional)   Definition: Orbital Petri Nets

49. 5. Orbital Petri Nets: A Promising Approach (Enabling, Firing Rule) 49 8/12/2018 P1 P2 P3 t1 [1,50] [2,100]   [1,70]  

50. 5. Orbital Petri Nets: A Promising Approach (Enabling, Firing Rule) 50 8/12/2018 t1 t2 [1,50] [1,80] [1,100] [1,60] [2,130] [2,20]       Example: P1 P2 P3 P4 P5 P6

51. 51 Orbital Petri Nets for studying Satellites/Debris Collisions is Recently our Research Project

52. 52