The algebra of processes VIII - the distributive laws

I want to first say something about the abstract setting. In the arXiv paper (arXiv:0909.4136 ) we considered a more complicated notion of process (mentioned in the second post of this series) with nine graphs, and we described many operations. We now believe that this definition was too general, and instead a process should consist of five graphs A,B,X,Y, G and four morphisms δ₀: G → A,  δ₁: G → B, γ₀: X → G, γ₁: Y → G  as we have been discussing in these posts.




What I will describe is essentially what we have written in the paper A Formalization of the IWIM Model, Coordination 2000, SLN in CS. That paper was however written for a computer science conference and was not sufficiently abstract, and was without data types.

I have said that such a thing is an arrow in Cospan(Graph/AxB) and the operations there are composition (denoted G;H)and sum (denoted G+H).

But such a thing also belongs to another category. Let T be the three object category which is a model of a cospan (that is, has a central object and two arrows one from each of the other objects into the central object). The a process is also and arrow in Span(Graph ^T) in the following way:

The central arrows are the deltas and gammas; the lefthand side and the right hand side consist of identities. The whole diagram is a span of cospans, that is, an arrow in  Span(Graph ^T).
The composition in this category will be denoted G•H and the tensor G⊗H.

Now the parallel  operations distribute over the sequential ones in a particular way. I describe one:
Consider the processes G with left parallel interface A, right parallel interface B, and processes H,K with  left parallel interface B, right parallel interface C. Let G=G₀;G₁ be the tabulation of G considered as a cospan (of spans) (that is, G₀ is the half of G pointing backward; G₁ is the part pointing forward).

 Then G•(H;K)=(G₀ •H);(G₁•K).


I will try to say something of the meaning of this law in the next post.
Suffice it to say here that this law (and the other similar ones) allow the flattening of a hierarchical system.
See the Coordination paper above for an example.

Another paper with the span-cospan algebra in a probabilistic context is:
Luisa de Francesco Albasini, Nicoletta Sabadini, Robert F. C. Walters: The compositional construction of Markov processes II. RAIRO - Theor. Inf. and Applic. 45(1): 117-142 (2011)
An early version available at arXiv:1005.0949v1.
The operations corresponding to the ones we have discussed are called parallel, parallel-with-communication, local sum, and local sequential.