On the algebra of processes

The following is an abstract submitted to a conference (only half a page was permitted). I would like expand a little here on the matter in the next day or so.

--------------------------------------------
Abstract: On the algebra of processes


Process algebras were introduced by Hoare, Milner and Bergstra-Klop to extend the theory of sequential computation to include parallel and concurrent computation. The basic idea of Milner was to add a parallel operation symbol to the successful algebra of Kleene of regular languages. Notice that Kleene's algebra is an algebra of behaviours rather than of programs/automata/machines. Milner's algebra inherits that fact, and is more concerned with observation of systems rather than systems themselves.

In 1997 Katis, Sabadini and I proposed the category Span(Graph) as a parallel algebra of automata, and (in 2000) Cospan(Graph) as the associated sequential algebra. The ideas were successively developed with collaborators, including R. Rosebrugh. In 2004 at the meeting in Vancouver I proposed with Sabadini the more abstract notion of a process (in a topos C) with parallel and sequential interfaces, namely an object G together with four objects A, B, X, Y and four arrows d0:G->X, d1: G->Y, g0:A->G , g1:B->G. Such a diagram may be regarded as a span of cospans or a cospan of spans. It exists as an arrow in two monoidal categories: Span((A+B)\C) (with parallel operations), and Cospan(C/(XxY)) (with sequential operations). Both of these categories have commutative Frobenius structures on the objects. Processes may be combined in parallel in the first category and in sequence in the second. Alternating these operations leads to hierarchical systems.

We will describe recent developments including distributive laws between the parallel and sequential operations, which permit the flattening of hierarchy. In fact, the combined algebra forms a kind of ring of processes.
-------------------------------------