## Wednesday, April 30, 2014

### On the algebra of processes III

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

Let us now assume that the graphs may be infinite. We will however make some finiteness assumptions
which correspond to discrete aspects of the processes.

Consider a cospan of graphs labelled in alphabet A,  X ← G → Y. First we will take the alphabet A to be finite. We could make a less drastic assumption but I want to concentrate attention on X, Y, and G.
A consequence of the fact that A is finite is that G breaks up into subgraphs Ga, one for each element a of A, but all with the same vertex set vert(G).

In considering infinite state processes with discrete control we assume that transitions occur at threshold values. The assumption is that the set of states (or vertices) of G breaks up into a finite disjoint union of sets,
for example  vert(G)=U1+U2+...+Un.

What happens to a graph G when you break up its vertex set as a disjoint union  U1+U2+..+Un?  For each i,j you get the set of edges from Ui to Uj which we shall call G(i,j). There are domain and codomain functions Ui  ←  G(i,j)  →  Uj ; that is a span from Ui to Uj . So a graph breaks up into a matrix of spans. This is just the fact that Span(Sets) has direct sums and a graph is an endo-arrow in Span(Sets).

What I have said about the graph G also happens to each graph Ga .

From this matrix of spans we can draw a finite graph with n-vertices  U1 ,  U2 , ..., Un , and edges labelled by spans of sets and letters of A. (We omit edges labelled by empty spans.)

I haven't spoken of the sets X and Y. The sets also break up (by extensivity) X=X1+X2+...+Xm, Y=Y1+Y2+...+Yk. The functions X → G and Y →  G also break up into functions, and we make one further assumption that all the parts of the functions  X → G and Y →  G are the identity function.

At the end of these assumptions a cospan of labelled graphs between  discrete graphs looks  like  a labelled version of the finite cospans we considered in Processes II, that is something like:

where the U's are possibly infinite sets, R, S,T,L and M are spans of sets, a and b are labels.

What this has to do with simple (Turing equivalent) sequential programming I will describe in the next post.

Labels: ,