Wednesday, February 01, 2012

Petri nets and multigraphs

This post is to explain a connection in this earlier post.

Graphs are an extremely useful tool in designing and planning, and there are a host of different types. Computer scientists often think of a graph as a binary relation from a set X to X. Another type well-known to category theorists is the following: a graph consists of two sets Arcs and Vertices and two functions, source and target : Arcs -> Vertices.
In drawing such a graph the vertices are usually represented as dots and the arcs as arrows (source and target tell you the beginning and end of arrows). But there is an alternative way of drawing graphs, in which the arcs are represented as boxes (perhaps not rectangles, but with a shape like a half moon or a triangle which indicates a directionality) and the vertices are on wires that enter and exit from an arc. Here is a graph represented in these two different ways:

Another closely related type of graph which I call multigraphs (not a standard name) is the following: a multigraph consists of two sets Arcs, Vertices, and two functions as before source and target but now these functions are from Arcs to Vertices* (the free monoid on vertices). It is clear that ordinary graphs are a special case, namely when the source and targets of arcs are single vertices (words of length one), but for picturing a multigraph the second way is better. You should think of the arcs as boxes and the vertices as nodes on wires. Then the source of an arc is a number of wires entering the box, and the target a number of wires exiting.
Here is an example of a multigraph written as arcs between words in vertices,  and pictured as boxes and wires:  multigraph {a:X->Z,  b:YX->W,  c: ZW->Y, d: W->X} with picture

The picture doesn't quite do justice to the multigraph because the source and target wires of an arc in  a multigraph have a definite order.
It is exactly this last fact which distinguishes multigraphs from Petri nets, but in my opinion it is an infelicity in the definition of Petri net. I have two reasons for this opinion: (i) that components in practice have an ordering on the input and on the output wires, and (ii) that multigraphs are appropriate for generating symmetric monoidal categories. I remember discussing this point with José Meseguer at AMAST in 1989 in Iowa, before his lecture at LICS in Asilomar, where he presented his paper with Ugo Montanari on behaviours of Petri nets as arrows in the free commutative monoidal category on a Petri net.
(Montanari and Meseguer define a P/T net as a   pair of functions from Arcs(=transitions) to the free commutative monoid  on Vertices(=places).)

Correction added: In fact the pictures of multigraphs above do not hide lose the order on the incoming wires. What is true is that in many pictorial representations of Petri nets an ordering is put on the incoming  "wires" which is not present in the definition.



Post a Comment

<< Home