On the algebra of processes II

I have decided to write a sequence of short posts explaining the ideas behind the abstract I recently posted. I forgot to mention in the abstract that there is a 2009 paper on Arxiv by Luisa de Francesco Albasini, Nicoletta Sabadini and me with some more explanation of our ideas (arXiv:0909.4136 ). It was a summary of thoughts over the summer holiday in Santa Caterina Valfurva that year and was never published. It lacks the distributive laws, and promises to later "fill out details of matters sketched" which promise I hope to partially fulfill in these posts.


In that paper the definition of process is a bit different to the one in the abstract:

The definition in the abstract is an interesting limited special case.

An easier reference to this work (but with probabilistic case in mind) are the slides to my talk at CT 2010 in Genova.

But let me begin by starting with something much simpler:

THE ALGEBRA OF SEQUENTIAL PROCESSES AS COSPANS(GRAPH/A): Finite state case

First let's look at the finite state case, non-deterministic finite state automata (NFA) with Kleene operations. An NFA is a graph labelled in an alphabet A, with a specified initial state and a set of final states. The type of graph allowed is more limited than we have in mind, namely it is a set Q of states and a subset of QxQ. An example with alphabet {a,b,c} initial state q0, final states q2,q3,q4

Now looking at this picture you can see that we can make a small generalization of NFA by taking general graphs which have a set of vertices, a set of edges and domain and codomain functions, and taking not just initial and final states but a function into the states on the left from a finite set, and a similar function into the states on the right - that is a cospan of graphs labelled in A between discrete graphs.

Putting NFA's in Cospan(Graph/A) has an immediate advantage. Cospan(Graph/A) has a composition by pushout, a symmetric monoidal structure from disjoint sum, a compact closed structure which permits feedback, and a Frobenius algebra structure on the objects.

Of course there are Kleene operations on NFA's which have a similar intent but are much less canonical. For example, every automaton can be constructed from single arrow automata using the operations of Cospan(Graph/A). This is NOT true for Kleene operations. More, Cospan(Graph/A)  between discrete graphs is free symmetric monoidal category with ...  on the single arrow cospans. These facts together with a compositional proof of Kleene's theorem on regular languages can be found here and here.

One might object that to prove Kleene's theorem there is no need to go into these categorical details, and that traditional NFA's give the proof much more efficiently. (One could give essentially the same elementary proof using cospans - there is a complication - one needs to keep track of the languages between any pair of entry/exit states, not just between initial and final.) 

However if one is interested in NFA's as control structures in sequential programming (instead of as language recognizers) there is a real advantage in considering cospans as I hope to show in the next post.