The algebra of processes VI
The PARALLEL ALGEBRA of PROCESSES Span(Graph)
We have just described Cospan(Graph/A) as a sequential algebra. However if we take A
×
B instead of A, a cospan in Graph/(A×B) from X to Y consists of four morphisms of graphs: X → G, Y → G, G → A, and G → B, where here A and B are thought of as graphs with a single vertex, and edge sets being A and B respectively.
But this is exactly an example of a process as defined in the first post of this series. X and Y are the sequential interface, A and B the parallel interface. Such a process is in Cospan(Graph/(A
×
B)), the sequential algebra, but also in Span((X+Y)\Graph), the parallel algebra.
To concentrate on the parallel aspects I will assume here that X= Y = 0 and consider only Span(Graph).
In the case that A,B and G are finite the algebra is discussed in many of our papers, starting with the 1997 AMAST paper. A copy can be found here: http://comocategoryarchive.com/Archive/people/walters/papers/pdf/1997-span-graph.pdf.
What I would like to discuss here is the case when G is infinite. We assume that A and B are finite and, as before, that the vertex set of G is a (given) finite sum of sets U1+U2 +...+U n . As before the graphs Ga,b
which project to a in A, and b in B, break up into spans Ga,b;i,j (i,j=1,2,...,n).
We can draw the span G as a box containing a graph with vertices Ui and for each a,b in A × B an edge from i to j labelled Ga,b;i,j. As usual we omit edges for which the span is empty. We draw ports on the component, one on the left labelled A, and one on the right labelled B (if A or B are given as products we draw multiple ports.)
Next I want to describe composition in Span(Graph) and give an example or two. Essentially the algebra is that of our papers for finite span graph but states labelled by sets, and edges labelled by spans of sets.
In the case that A,B and G are finite the algebra is discussed in many of our papers, starting with the 1997 AMAST paper. A copy can be found here: http://comocategoryarchive.com/Archive/people/walters/papers/pdf/1997-span-graph.pdf.
What I would like to discuss here is the case when G is infinite. We assume that A and B are finite and, as before, that the vertex set of G is a (given) finite sum of sets U1+U2 +...+U n . As before the graphs Ga,b
which project to a in A, and b in B, break up into spans Ga,b;i,j (i,j=1,2,...,n).
We can draw the span G as a box containing a graph with vertices Ui and for each a,b in A × B an edge from i to j labelled Ga,b;i,j. As usual we omit edges for which the span is empty. We draw ports on the component, one on the left labelled A, and one on the right labelled B (if A or B are given as products we draw multiple ports.)
Next I want to describe composition in Span(Graph) and give an example or two. Essentially the algebra is that of our papers for finite span graph but states labelled by sets, and edges labelled by spans of sets.
Labels: category theory, computing
posted by Unknown at 4:29 AM
0 Comments:
Post a Comment
<< Home