Technical Report. Menlo Park, CA, USA: SRI International, January 1988. Revised June, 1989.
Also in: Information and Computation, Vol. 88, No. 2, pages 105-155. October 1990.
Abstract: The authors start by remarking that place/transition Petri nets can be viewed as ordinary, directed graphs equipped with two algebraic operations corresponding to parallel and sequential composition of transitions. New morphisms are defined, mapping single, atomic transitions into whole computations. Categories equipped with products and coproducts (corresponding to parallel and nondeterministic compositions) are introduced for Petri nets, and Petri net duality is expressed as a duality functor. A tensor product is defined on nets, and their category is proved to be symmetric monoidal closed. This construction is generalized to a large class of algebraic theories on graphs. These results provide a formal basis for expressing the semantics of concurrent languages in terms of Petri nets. They also provide a new understanding of concurrency in terms of algebraic structures over graphs and categories.
Keywords: monoid; place/transition net; parallel (and) sequential composition; morphism; category (with) product (and) coproduct; coproducts (corresponding to parallel and nondeterministic semantics (of) concurrent language.