Computer Laboratory

Technical reports

Petri nets, algebras and morphisms

Glynn Winskel

38 pages

Abstract

It is shown how a category of Petri nets can be viewed as a subcategory of two sorted algebras over multisets. This casts Petri nets in a familiar framework and provides a useful idea of morphism on nets different from the conventional definition – the morphisms here respect the behaviour of nets. The categorical constructions with result provide a useful way to synthesise nets and reason about nets in terms of their components; for example various forms of parallel composition of Petri nets arise naturally from the product in the category. This abstract setting makes plain a useful functor from the category of Petri nets to a category of spaces of invariants and provides insight into the generalisations of the basic definition of Petri nets – for instance the coloured and higher level nets of Kurt Jensen arise through a simple modificationof the sorts of the algebras underlying nets. Further it provides a smooth formal relation with other models of concurrency such as Milner’s Calculus of Communicating Systems (CCS) and Hoare’s Communicating Sequential Processes (CSP).

Full text

PDF (2.1 MB)

BibTeX record

@TechReport{UCAM-CL-TR-79,
  author =	 {Winskel, Glynn},
  title = 	 {{Petri nets, algebras and morphisms}},
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-79.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-79}
}