On the Relative Expressiveness of Petri Nets, Event Structures and
Process Algebras
Rob van Glabbeek
Stanford University
February 1998
In this talk I consider mappings from expressions in system
description languages like CCS and CSP to Petri nets and vice versa.
I recall two methods for associating a Petri net to such a process
expression: the standard compositional approach where recursion is
dealt with using fixed point techniques, and a variant due to Ursula
Goltz in which recursion is implemented by redirecting arcs backwards
to initial places. The former approach always yields a so-called safe
flow net; recursion typically gives rise to infinite nets. The latter
approach works for the subclass of process expressions where in the
scope of a recursion construct only prefixing, independent parallel
composition and guarded choice is allowed; but always yields finite
S/T-nets. The two approaches are identical for recursion-free process
expressions; in general they agree up to fully concurrent bisimulation
equivalence. Here I extend the latter approach to deal with unguarded
recursion. I also show that for every finite S/T-net there exists a
process expression in the mentioned subclass whose semantics, up to
fully concurrent bisimulation, is that net. Moreover, every finite
safe flow net is denoted up to event-structure isomorphism by a
recursion-free process expression.