Petri nets are a popular and powerful formal model for the analysis and modelling of concurrent systems, and a rich theory has developed around them. Petri nets are taught to undergraduates, and also used by industrial practitioners. This book focuses on a particular class of petri nets, free choice petri nets, which play a central role in the theory. The text is very clearly organised, with every notion carefully explained and every result proved. Clear exposition is given for place invariants, siphons, traps and many other important analysis techniques. The material is organised along the lines of a course book, and each chapter contains numerous exercises, making this book ideal for graduate students and research workers alike.
Author(s): Jorg Desel, Javier Esparza
Series: Cambridge Tracts in Theoretical Computer Science 40
Publisher: CUP
Year: 1995
Language: English
Pages: 254
Tags: Математика;Дискретная математика;
1 Introduction......Page 10
1.1 Petri nets......Page 11
1.2 Free-choice Petri nets......Page 14
1.3 Properties......Page 17
1.4 Structure of the book......Page 18
2.1 Mathematical preliminaries......Page 22
2.2 Nets and their properties......Page 24
2.3 Systems and their properties......Page 33
2.4 S-invariants and T-invariants......Page 39
3.1 S-systems......Page 50
3.2 T-systems......Page 55
4.1 Free-choice systems......Page 72
4.2 Stable predicates: siphons and traps......Page 75
4.3 Commoner's Theorem......Page 78
4.4 The non-liveness problem is NP-complete......Page 89
4.5 Minimal siphons......Page 92
4.6 Liveness and deadlock-freedom......Page 94
5.1 The S-coverability Theorem......Page 98
5.2 Derived results......Page 104
5.3 The T-coverability Theorem......Page 108
5.4 Derived results......Page 116
6.1 Characterizations of well-formedness......Page 120
6.2 The non-well-formed case......Page 123
6.3 The well-formed case......Page 130
6.4 Derived results......Page 137
7 Reduction and synthesis......Page 144
7.1 Basic notions......Page 145
7.2 The reduction rules......Page 146
7.3 An example of reduction......Page 156
7.4 Completeness......Page 158
7.5 Synthesis rules......Page 170
8.1 Existence of home markings......Page 178
8.2 A characterization of the home markings......Page 183
8.3 Derived results......Page 192
9 Reachability and shortest sequences......Page 194
9.1 The Reachability Theorem......Page 195
9.2 The Shortest Sequence Theorem......Page 204
10.1 Asymmetric-choice nets......Page 216
10.2 A necessary condition for well-formedness......Page 219
10.3 A sufficient condition for well-formedness......Page 223
Index......Page 244
List of symbols......Page 250
List of main results......Page 252
