### 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

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

What happens to a graph G when you break up its vertex set as a disjoint union U

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

From this matrix of spans we can draw a finite graph with n-vertices U

I haven't spoken of the sets X and Y. The sets also break up (by extensivity) X=X

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.

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

_{1}+U_{2}+...+U_{n}.What happens to a graph G when you break up its vertex set as a disjoint union U

_{1}+U_{2}+..+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

_{1 }, U_{2}, ..., 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

_{1}+X_{2}+...+X_{m}, Y=Y_{1}+Y_{2}+...+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:

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

Labels: category theory, computing

## 0 Comments:

## Post a Comment

<< Home