The algebra of processes XI

Previous post in this series is here.

We have been thinking about categorical algebra for computer science now for 25 years. I want to discuss the problems of thinking seriously about two distinct disciplines, and how one might avoid the danger of falling between two stools.


There is clearly a problem at the level of exposition. We have tended to write for category theorists, but often in a slightly watered down form, so that the result is not interesting to category theorists, and at the same time obscure to computer scientists. Some of our articles are purely mathematical and I suspect category theorists are not aware that they are written to support our computer science investigations.  I think the solution is to write two quite different types of article, one for category theorists, and the other for computer scientists.

The more serious problem is at the level of research. We think that some apparent applications of  category theory to computer science are superficial, arising from the casual recognition of some categorical constructions in areas already developed. In order to avoid this tendency we have always sought to be principally advised by the computer science problem rather than category theory. This has the effect that we sometimes fail to say obvious categorical things.

As an example, in the recent ten posts on the algebra of processes I think we have given a distorted picture of the algebra by keeping our noses to the ground, and avoiding the more advanced categorical aspects.

Here in brief is a more advanced point of view of the categorical algebra of processes introduced in the previous ten posts. We begin with an elementary topos C and consider the bicategory Span(C). This has lots of nice structure and properties. (i) It is a symmetric monoidal (from product) bicategory with commutative separable algebra structure on the objects. (ii)  Composition and tensor preserve local colimits.  (iii) In particular tensor and composition commute with pi_0 of local reflexive graphs.
For objects A,B we may consider Cospan(Span(A,B)). (iv) These categories are symmetric monoidal with tensor coming from sum, and with commutative separable algebra structure on the objects. As a result of (iv) and the main theorem of the paper www.tac.mta.ca/tac/volumes/15/6/15-06.pdf there are expressions in the algebra Cospan(Span(A,B)) which represent labelled graphs. As a result of (iii), which is effectively a distributive law, the composition of local graphs in Span(C) is done as in the paper Span(Graph).

And so on. In this algebra we may describe classical sequential programming, and concurrent programming, as illustrated in the previous posts.

We will write two versions of the lecture I intended for the CT2014, one for category theorists and one for computer scientists. I hope this will allow us to avoid falling between two stools.