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 G_a, 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)=U₁+U₂+...+U_n.

What happens to a graph G when you break up its vertex set as a disjoint union  U₁+U₂+..+U_n?  For each i,j you get the set of edges from U_i to U_j which we shall call G(i,j). There are domain and codomain functions U_i  ←  G(i,j)  →  U_j ; that is a span from U_i to U_j . 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 G_a .

From this matrix of spans we can draw a finite graph with n-vertices  U₁ ,  U₂ , ..., U_n , 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=X₁+X₂+...+X_m, Y=Y₁+Y₂+...+Y_k. 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.