David / Alla Discrete, Continuous, and Hybrid Petri Nets

1. Auflage 2005
ISBN: 978-3-540-26821-5
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 526 Seiten

Petri nets do not designate a single modeling formalism. In fact, newcomers to the field confess sometimes to be a little puzzled by the diversity of formalisms that are recognized under this 'umbrella'. Disregarding some extensions to the theoretical modeling capabilities, and looking at the level of abstraction of the formalisms, Condition/Event, Elementary, Place/Transition, Predicate/Transition, Colored, Object Oriented... net systems are frequently encountered in the literature. On the other side, provided with appropriate interpretative extensions, Controled Net Systems, Marking Diagrams (the Petri net generalization of State Diagrams), or the many-many variants in which time can be explicitly incorporated -Time(d), Deterministic, (Generalized) Stochastic, Fuzzy...- are defined. This represents another way to define practical formalisms that can be obtained by the 'cro- product' of the two mentioned dimensions. Thus Petri nets constitute a modeling paradigm, understandable in a broad sense as 'the total pattern of perceiving, conceptualising, acting, validating and valuing associated with a particular image of reality that prevails in a science or a branch of science' (Thomas S. Kuhn).

Autoren/Hrsg.

David, René

Alla, Hassane

Inhaltsverzeichnis

1;Foreword;5
2;Preface;8
2.1;Acknowledgements;10
3;Contents;12
4;Notation;18
5;Bases of Petri Nets;22
5.1;1.1 BASIC CONCEPTS;22
5.1.1;1.1.1 Places, Transitions and Arcs;22
5.1.2;1.1.2 Marking;23
5.1.3;1.1.3 Firing of a Transition;24
5.1.4;1.1.4 Autonomous and Non-autonomous Petri Nets;25
5.1.5;1.1.5 The Essential Characteristics;26
5.2;1.2 SPECIAL PETRI NETS;26
5.2.1;1.2.1 Particular Structures;27
5.2.2;1.2.2 Abbreviations and Extensions;30
5.3;1.3 MODELING OF SOME CONCEPTS;38
5.4;NOTES and REFERENCES;41
6;Properties of Petri Nets;42
6.1;2.1 PRESENTATION OF THE MAIN PROPERTIES;42
6.1.1;2.1.1 Notations and Definitions;42
6.1.2;2.1.2 Bounded Petri Net, Safe Petri Net;45
6.1.3;2.1.3 Liveness and Deadlock;46
6.1.4;2.1.4 Conflicts;51
6.1.5;2.1.5 Invariants;55
6.2;2.2 SEEKING THE PROPERTIES OF PETRI NETS;58
6.2.1;2.2.1 Graph of Markings and Coverability Root Tree;58
6.2.2;2.2.2 Linear Algebra;62
6.2.3;2.2.3 Reduction Methods Preserving Some Properties;72
6.2.4;2.2.4 Other Results;74
6.2.5;2.2.5 Concluding Remarks;77
6.3;NOTES and REFERENCES;80
7;Non-Autonomous Petri Nets;82
7.1;3.1 INTRODUCTION;82
7.2;3.2 SYNCHRONIZED PETRI NETS;84
7.2.1;3.2.1 Principle;85
7.2.2;3.2.2 Iterated Firing On Occurrence of an External Event;91
7.2.3;3.2.3 Properties of the Synchronized PNs;97
7.3;3.3 INTERPRETED PETRI NETS;105
7.3.1;3.3.1 Definition of a Control Interpreted Petri Net;106
7.3.2;3.3.2 Interpretation Algorithm of a Control Interpreted PN;110
7.3.3;3.3.3 Interpreted PN Without Outputs: Generalization of the Concept of Synchronized PN;113
7.4;3.4 TIMED PETRI NETS;114
7.4.1;3.4.1 General Information;114
7.4.2;3.4.2 Constant Timing;117
7.4.3;3.4.3 Stochastic Petri Nets;124
7.5;NOTES and REFERENCES;129
8;Autonomous Continuous and Hybrid Petri Nets;132
8.1;4.1 AUTONOMOUS CONTINUOUS PETRI NETS;132
8.1.1;4.1.1 From Discrete Petri Net To Continuous Petri Net;132
8.1.2;4.1.2 Definition;135
8.1.3;4.1.3 Reachability and Conflicts;137
8.2;4.2 AUTONOMOUS HYBRID PETRI NETS;143
8.2.1;4.2.1 Intuitive presentation;143
8.2.2;4.2.2 Definition;145
8.2.3;4.2.3 Reachability and conflicts;147
8.3;4.3 PROPERTIES OF AUTONOMOUS CONTINUOUS AND HYBRID PETRI NETS;154
8.3.1;4.3.1 Definitions and Properties Similar for Discrete and Continuous Petri Nets;154
8.3.2;4.3.2 Reachability and Limit Reachability for a Continuous Petri Net;156
8.3.3;4.3.3 e- Liveness for a Continuous Petri Net;159
8.3.4;4.3.4 Lim-Liveness for a Continuous Petri Net;160
8.4;4.4 EXTENDED HYBRID PETRI NETS;164
8.4.1;4.4.1 Threshold Test;164
8.4.2;4.4.2 Zero Test and Arc Weight 0+;165
8.4.3;4.4.3 Marking 0+;167
8.4.4;4.4.4 Definition;168
8.5;NOTES and REFERENCES;169
9;Timed Continuous Petri Nets;170
9.1;5.1 DEFINITION OF THE MODEL;170
9.1.1;5.1.1 Limit Case of a Discrete Timed Petri Net;171
9.1.2;5.1.2 Analysis of Some Basic Behaviors;172
9.1.3;5.1.3 Definitions;184
9.2;5.2 CONFLICTS;191
9.2.1;5.2.1 Existence of an Actual Conflict;191
9.2.2;5.2.2 Conflict Resolution;192
9.3;5.3 SPEED CALCULATION ALGORITHMS;194
9.3.1;5.3.1 There is No Structural Conflict;195
9.3.2;5.3.2 Resolution By Priorities;197
9.3.3;5.3.3 Resolution By Sharings And Priorities;210
9.3.4;5.3.4 Complete Algorithm For All IB-states;223
9.4;5.4 PROPERTIES;226
9.4.1;5.4.1 Illustratory Examples;226
9.4.2;5.4.2 General Properties;229
9.4.3;5.4.3 Modeling Power;233
9.5;5.5 MAXIMAL SPEEDS FUNCTIONS OF TIME;235
9.6;NOTES and REFERENCES;237
10;Timed Hybrid Petri Nets;240
10.1;6.1 DEFINITION OF THE MODEL;240
10.1.1;6.1.1 Intuitive Presentation;241
10.1.2;6.1.2 Events To Be Considered;242
10.1.3;6.1.3 Conflict Resolutions;244
10.1.4;6.1.4 Flow Rate and Maximal Firing Speed;247
10.1.5;6.1.5 Formal Definitions;249
10.2;6.2 ALGORITHM;256
10.2.1;6.2.1 Resolution for a Case 4 Conflict;257
10.2.2;6.2.2 Consequences of Various Events;262
10.2.3;6.2.3 Timed Hybrid PNs Automatically Treated in Algorithm 6.1;264
10.2.4;6.2.4 Algorithm for Building the Evolution Graph;270
10.2.5;6.2.5 Resolution of a Case Not Treated by Algorithm 6.1;275
10.3;6.3 VARIANTS OF THE MODEL;276
10.3.1;6.3.1 Synchronized D-Transitions;276
10.3.2;6.3.2 Stochastic Timings for D-Transitions;279
10.3.3;6.3.3 C-Transitions with Flow Rates Functions of Time;280
10.4;6.4 EXTENDED TIMED HYBRID PETRI NETS;282
10.4.1;6.4.1 Modeling of Zero Buffers;283
10.4.2;6.4.2 Arc Weight 0+ for Testing if a C-Place is Empty;286
10.4.3;6.4.3 Pure Delay of a Continuous Flow;289
10.4.4;6.4.4 Conclusion on Timed Extended Hybrid Petri Nets;296
10.5;NOTES and REFERENCES;297
11;Hybrid Petri Nets with Speeds Depending on the C-Marking;300
11.1;7.1 APPROXIMATION OF TIMED DISCRETE SYSTEMS BY VHPNs;300
11.1.1;7.1.1 Weakness of Basic Timed Hybrid PNs for Small Numbers;301
11.1.2;7.1.2 Simple Cases of Variable Speed Hybrid PN;302
11.1.3;7.1.3 General Case of VHPN;306
11.1.4;7.1.4 Application Examples ;315
11.2;7.2 ASYMPTOTIC HYBRID PETRI NETS ( AHPNs);320
11.2.1;7.2.1 A C-Transition Has a Single Input C-Place;321
11.2.2;7.2.2 Several Input C-Places;326
11.2.3;7.2.3 Generalization;327
11.2.4;7.2.4 Differences Between VHPN and AHPN Behaviors;331
11.3;7.3 OTHER MODELS;335
11.3.1;7.3.1 Liquid Flow;335
11.3.2;7.3.2 Differential Hybrid Petri Nets;336
11.3.3;7.3.3 Transfer Line with Operation-Dependent Failures;339
11.4;NOTES and REFERENCES;340
12;Postface;342
12.1;Post.1 USE & ANALYSIS OF VARIOUS PN MODELS;342
12.2;Post.2 RELATIONS AMONG KINDS OF HYBRID PNs;343
13;Appendices;348
13.1;Appendix A Regular Expressions and Languages;348
13.2;Appendix B Conflict Resolution;350
13.3;Appendix C Elements of Graph Theory;354
13.4;Appendix D Algebra of Events;356
13.5;Appendix E About Grafcet;360
13.6;Appendix F Modeling Power of Synchronized PNs;366
13.7;Appendix G Timed Petri Nets Are Special Cases of Synchronized Petri Nets;368
13.8;Appendix H Time Petri Nets;374
13.9;Appendix I Linearity of the Fundamental Equation for Continuous Petri Nets;378
13.10;Appendix J Notation 0+ and Non-Standard Analysis;382
13.11;Appendix K Sharing Between Two Transitions;384
13.12;Appendix L Graph of Relations Among Conflicts;390
13.13;Appendix M Piecewise Constant Maximal Speeds;394
13.14;Appendix N From Hybrid PNs to Hybrid Automata;402
13.15;Appendix O P&T-Timed Petri Nets and Modeling Power;408
14;Exercises;414
15;Solutions to Exercises;454
16;References;522
17;Index;536