Span(Graph) III: Circuits with feedback

Previous post in this series; next post in the series.

The two main operations in $\bf Circ$ are composition and parallel as for straight-line circuits, and there are a variety of constants.

Today we describe the operation of composition of circuits with feedback in $\bf Circ$.

Read more »

Span(Graph) II: Circuits with feedback

Previous Span(Graph) post; next Span(Graph) post.

As an introduction to ${\bf Span(Graph)}$ I will describe how to extend the category of straight-line circuits to allow circuits with state and feedback. But before doing that I would like to point out a couple of things about straight-line circuits.

Read more »

Span(Graph) I

Next Span(Graph) post.


I have decided to write a series of tutorial posts about Span(Graph) since I think this work has been unfairly neglected. I am simultaneously introducing a little TeX into the blog, at the encouragement of Keith Harbaugh.

We begin with a simpler category as an algebra of straight line circuits which we will use as motivation for then in a later post introducing ${\bf Span}({\bf Graph})$.
Read more »

The algebra of processes XI

Previous post in this series is here.

We have been thinking about categorical algebra for computer science now for 25 years. I want to discuss the problems of thinking seriously about two distinct disciplines, and how one might avoid the danger of falling between two stools.
Read more »

Shag on a rock

Well, it turns out that I cannot go to the Cambridge meeting, Category Theory 2014, after all. I will be having some treatment next week. I will try to put up on arXiv an account of the lecture I intended to give.

In an earlier post I said that my talk seemed to have no connection with any other that I could see from the titles. However looking a bit more closely perhaps there are one or two related.
Read more »

The algebra of processes X

This is a post in a series: the previous post is here. Next post is here.

Read more »

The algebra of processes IX

I have had some problems so there has been a break in this series of posts. But also I was not quite sure how to explain what I called the distributive laws with the rather primitive mathematical resources of my blogspot. I should really find out how to incorporate TeX.
Read more »

The algebra of processes VIII - the distributive laws

I want to first say something about the abstract setting. In the arXiv paper (arXiv:0909.4136 ) we considered a more complicated notion of process (mentioned in the second post of this series) with nine graphs, and we described many operations. We now believe that this definition was too general, and instead a process should consist of five graphs A,B,X,Y, G and four morphisms δ₀: G → A,  δ₁: G → B, γ₀: X → G, γ₁: Y → G  as we have been discussing in these posts.

Read more »

The algebra of processes VII

PARALLEL PROGRAMMING in Span(Graph)

Last post I promised to give an example of a parallel program. Here is a very simple one which is the parallel composite of two components both having state space N+N+N (N= natural numbers).
I have distinguished the different summands by subscripts to make the description of the composite clearer:

Read more »

The algebra of processes VI

The PARALLEL ALGEBRA of PROCESSES Span(Graph)

We have just described Cospan(Graph/A) as a sequential algebra. However if we take A × B instead of A, a cospan in Graph/(A×B) from X to Y  consists of four morphisms of graphs: X → G, Y → G, G → A, and G → B, where here A  and B are thought of as graphs with a single vertex, and edge sets being A and B respectively.

But this is exactly an example of a process as defined in the first post of this series. X and Y are the sequential interface, A and B the parallel interface. Such a process is in Cospan(Graph/(A × B)), the sequential algebra, but also in Span((X+Y)\Graph), the parallel algebra.

Read more »

The algebra of processes V

SEQUENTIAL PROGRAMMING in Cospan(Graph) continued:

We are now not interested in the alphabet A, but just in writing sequential programs whose input/output behaviour yield partial functions, so we take A to be a one letter alphabet and ignore it.

There is an operation I have not introduced which strictly speaking is not in Cospan because it is a little bit of parallelism, which however does not involve any parallel communication. We will see later that it is an operation which involves Span and Cospan.

Read more »

On the algebra of processes IV

In this post I want to begin describing simple sequential programming in terms of Cospan(Graph/A).  First let's look at two examples of (infinite) cospans:

N is the natural numbers. The span "error" is the partial function which takes 0 to error. The span "pred" is the partial function which takes n to n-1 if n is positive. The span "zero" is the function on one point that takes the value 0. The span "succ" is the successor function.

Read more »

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).
Read more »

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.
Read more »

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
Read more »

Racks and Tangled Circuits

This is just a link  (https://dl.dropboxusercontent.com/u/92056191/walters-aurelio-talk-24062013.pdf) to the slides of the lecture I gave at the conference this week in Milan in memory of Aurelio Carboni.  The lecture starts with some memories of working with Aurelio (I said more at the conference!) putting some recent work in context.

I noticed while writing the slides that I had not separated the properties of racks sufficiently from those of the new notion of irack - I will probably write up a clearer version for arxiv.

Update: The promised arxiv paper is at http://arxiv.org/abs/1307.5404.

Sequential versus parallel

We (Sabadini, Schiavio and I) have just finished a paper on the algebra and geometry of networks (which I must remember to put on Arxiv). In any case, we wanted to give one example involving Petri nets.

The difficulty of writing something precise about Petri nets is that there is huge literature, with an enormous number of variations in definitions of nets and their behaviours. We chose to talk about the simplest version we could find.

Most concurrent systems consist of sequential components which have occasional communication at critical points.  In writing about Petri nets one thing struck me (us) which I had not realized so clearly before: a sequential process  with say n states is represented as a Petri net with n parallel places. This means that the Petri net of an n state sequential process has an exponential (in n) number of possible states (markings).
Of course only n are intended to be reachable.

It seems to me to be crucial to separate the sequential from the parallel aspects of programs. A correct algebra of programs should have two types of operations (one sequential,  of colimit type , the other parallel, of type limit). The relation between them should be the exactness which we see in categories of spaces.

Even in classical sequential programming there is the beginning of this phenomenon, namely that if then else is based on the distributive law of products over sums.

IC chip orientation

In a previous post I indicated how to sketch a picture of a monoidal graph (or multigraph). A monoidal graph consists of two sets Comp (the components) and Wire (the wires) and two functions dom, cod: Comp -> Wire* (where Wire* is the free monoid on the wires). If dom of a component has length n then the component has n (ordered) left-hand ports; if cod of a component has length m then the component has m right-hand (ordered) ports. The functions dom and cod say to which wire a port is attached.
This means that a component looks very like a traditional dual in-line chip.
Read more »

Spantools

Filippo Schiavio's programs for calculating behaviours of systems described by expressions in Span(Graph), with a graphical output, is now available at  https://sourceforge.net/projects/spantool.
Read more »

Why a process algebra is not an algebra of processes

I'd like to explain why I think a process algebra is not an algebra of processes.
I need to explain some minimal properties that an algebra of processes should have. Firstly finite state automata should be processes. Secondly such an algebra should have abstract operations; that is, the operation applied to isomorphic automata should produce isomorphic automata.
 I will now demonstrate why these two properties are not satisfied by process algebras.

Read more »