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 tradeoff 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 freechoice Petri
nets. Eike Best coined the term `freechoice hiatus' in 1986 to express
that, whereas there exists a rich and elegant theory for freechoice
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 freechoice 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:
 Introduction
 Petri nets
 Freechoice Petri nets
 Properties
 Structure of the book
 Analysis techniques for Petri nets
 Mathematical preliminaries
 Nets and their properties
 Systems and their properties
 Sinvariants and Tinvariants
 Ssystems and Tsystems
 Ssystems
 Tsystems
 Liveness in freechoice systems
 Freechoice systems
 Stable predicates: siphons and traps
 Commoner's Theorem
 The nonliveness problem is NPcomplete
 Minimal siphons
 Liveness and deadlockfreedom
 The Coverability Theorems
 The Scoverability Theorem
 Derived results
 The Tcoverability Theorem
 Derived results
 The Rank Theorem
 Characterizations of wellformedness
 The nonwellformed case
 The wellformed case
 Derived results
 Reduction and synthesis
 Basic notions
 The reduction rules
 An example of reduction
 Completeness
 Synthesis rules
 Home markings
 Existence of home markings
 A characterization of the home markings
 Derived results
 Reachability and shortest sequences
 The Reachability Theorem
 The Shortest Sequence Theorem

Generalizations
 Asymmetricchoice nets
 A necessary condition for wellformedness
 A sufficient condition for wellformedness
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 softcover. If you are interested, follow
this link.
Back to: Javier Esparza