Petri nets are one of the most popular formal models of concurrent systems, used by both theoreticians and practitioners. The latest compilation of the scientific literature related to Petri nets, dating from 1991, contains 4099 entries, which belong to such different areas of research as databases, computer architecture, semantics of programming languages, artificial intelligence, software engineering and complexity theory. There are also several introductory texts to the theory and applications of Petri nets (see the bibliographic notes). The problem of how to analyze Petri nets -- i.e., given a Petri net and a property, how to decide if the Petri net satisfies it or not -- has been intensely studied since the early seventies. The results of this research point out a very clear trade-off between expressive power and analyzability. Even though most interesting properties are decidable for arbitrary Petri nets, the decision algorithms are extremely inefficient. In this situation it is important to explore the analyzability border, i.e., to identify a class of Petri nets, as large as possible, for which strong theoretical results and efficient analysis algorithms exist. It is now accepted that this border can be drawn very close to the class of free-choice Petri nets. Eike Best coined the term `free-choice hiatus' in 1986 to express that, whereas there exists a rich and elegant theory for free-choice Petri nets, few of its results can be extended to larger classes. Since 1986, further developments have deepened this hiatus, and reinforced its relevance in Petri net theory. The purpose of this book is to offer a comprehensive view of the theory of free-choice Petri nets. Moreover, almost as important as the results of the theory are the techniques used to prove them. The techniques given in the book make very extensive and deep use of nea! all the analysis methods indigenous to Petri nets, such as place and transition invariants, the marking equation, or siphons and traps. In fact, the book can also be considered as an advanced course on the application of these methods in Petri net theory.
Back to: Javier Esparza