J. Desel and J. Esparza: Free Choice Petri Nets
Cambridge Tracts in Theoretical Computer Science 40, 1995.


Abstract:

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.

Contents:

  1. Introduction
    1. Petri nets
    2. Free-choice Petri nets
    3. Properties
    4. Structure of the book
  2. Analysis techniques for Petri nets
    1. Mathematical preliminaries
    2. Nets and their properties
    3. Systems and their properties
    4. S-invariants and T-invariants
  3. S-systems and T-systems
    1. S-systems
    2. T-systems
  4. Liveness in free-choice systems
    1. Free-choice systems
    2. Stable predicates: siphons and traps
    3. Commoner's Theorem
    4. The non-liveness problem is NP-complete
    5. Minimal siphons
    6. Liveness and deadlock-freedom
  5. The Coverability Theorems
    1. The S-coverability Theorem
    2. Derived results
    3. The T-coverability Theorem
    4. Derived results
  6. The Rank Theorem
    1. Characterizations of well-formedness
    2. The non-well-formed case
    3. The well-formed case
    4. Derived results
  7. Reduction and synthesis
    1. Basic notions
    2. The reduction rules
    3. An example of reduction
    4. Completeness
    5. Synthesis rules
  8. Home markings
    1. Existence of home markings
    2. A characterization of the home markings
    3. Derived results
  9. Reachability and shortest sequences
    1. The Reachability Theorem
    2. The Shortest Sequence Theorem
  10. Generalizations
    1. Asymmetric-choice nets
    2. A necessary condition for well-formedness
    3. A sufficient condition for well-formedness

Archived copy: PDF file (20 MB)


Unfortunately, all the original files of the book are lost, so I can only archive a scanned copy here.
The copyright of this book lies by Cambridge University Press (CUP). I have got a verbal, informal authorization from CUP to archive a copy in my home page. I have mailed CUP several times in order to obtain an official, written permission, so far without answer. I understand that CUP has more important things to do than worrying about the copyright of a rather specialized research monography published in 1995 (14 years ago at the time of writing this); at the same time, I hope CUP will show understanding for my decision to make a copy available before getting their permission to do so.
In any case, please print only one copy of the book for your personal (noncommercial) use, and do not distribute the file further. The book can be purchased from the publisher in soft-cover. If you are interested, follow this link.

Back to: Javier Esparza