The algebra of processes IX

I have had some problems so there has been a break in this series of posts. But also I was not quite sure how to explain what I called the distributive laws with the rather primitive mathematical resources of my blogspot. I should really find out how to incorporate TeX.


To go back to the question of distributive laws in the CospanSpan algebra, the aim of such laws is as follows: Call an expression in the sequential cospan operations a Sigma expression and an expression in the parallel span operations a Pi expresssion. Then it should be possible to rewrite a Pi Sigma expression as a Sigma Pi expression (evaluating to the same process). The fact that this is possible is why I spoke in the abstract of a "ring of processes".

The example G•(H;K)=(G₀ •H);(G₁•K) from the last post was of this type. However the general problem of rewriting Pi Sigma  → Sigma Pi is more complicated. I think I will discuss only the special case of rewriting a product of Sigma expressions.

It will take me a little time to explain why Pi distributes over Sigma but the key fact is that the connected components of the product of two reflexive  graphs = the product of the connected components of each graph. If you check this you will see that it is closely  connected with the idea of asynchrony. 

(This is usually referred to as a property of reflexive coequalizers.)

Let's look at evaluating a Sigma expression. I am interested in the central object of the process. 

Caution: in this theory there are spans, cospans and graphs everywhere,  playing different roles. We have to keep things separate. So we are now going to ignore the fact that the central object of a process is a graph - just think of it as an object.

Remember that composing two cospans the new central object is a pushout of a span between the centres of each cospan.  But more generally the evaluation of a Sigma expression G is a sum of the central objects of the  cospans involved (excluding the constants) G1, G2, ..., Gn say, quotiented by spans Gi,j between them.    But the Gi's and the Gi,j's give a graph with vertex set G1+G2+...+Gn and edge set the sum of the spans. We call this graph e(G). The evaluation of the expression is the set Q of connected components of this graph e(G). Notice that if we add the identity spans to each object Gi the graph is reflexive and the quotient is unchanged.

Now consider another Sigma expression H with central objects of the cospans H1, H2, ... , Hm, spans Hk,l and evaluation R=connected components of e(H).

Consider then the Pi Sigma expression GxH. Its evaluation is
QxR = connected components e(G ) x connected components e(H)
       = connected components (e(G) x e(H)) since the graphs are reflexive.

But the graph e(G) x e(H) has vertex set the sum of the Gi x Hk, and edge set the sum of the spans Gi,j x Hk,l.

With a little effort this can be seen to be equivalent to a Sigma Pi expression as promised.

Remark: I know this is very brief. I will give two examples in the next post which may make the matter clearer.