Friday, October 09, 2009

On cospans and spans II

A little explanation of the paper http://arxiv.org/abs/0909.4136.

The aim of the paper is to describe discrete systems which communicate in parallel (that is, they are distributed in space) and evolve sequentially (the physical form of the system may change). This is an aim shared with so many (prior) authors it is invidious to begin a list but I must do so - Milner, Hoare, Petri, Zielonka, Nivat, ...

The basic model we take for a system is a graph of states and transitions.

To be capable of being combined with others a system must have borders, boudaries, or interfaces. Two types of interfaces are necessary. The first are sequential interfaces, drawing inspiration from the sequential operations of Kleene. A system must have (generalized) initial and terminal states. We commence more generally with two graph morphisms into the system.

A system with sequential interfaces is a cospan
$\usepackage[all]{xy}\xymatrix{ A\ar[r]^{\gamma_{0}}& G&B \ar[l]_{\gamma_1} }$
of graphs. The graph $G$ is the graph of the system; $A$, and $B$ are the graphs of the interfaces. Systems compose sequentially by pushout.

For the parallel interfaces we take inspiration from the model of circuits. Circuits have transitions which are reflected on the boundaries. We take here as our definition two graph morphisms out of the system

A system with parallel interfaces is a span
$\usepackage[all]{xy}\xymatrix{ X& G\ar[l]_{\partial_{0}}\ar[r]^{\partial_{1}}&Y }$
of graphs. The graph $G$ is the graph of the system; $X$, and $Y$ are the graphs of the interfaces. Parallel composition of systems is by pullback.

A system with sequential and parallel interfaces consists of a
commutative diagram of graphs and graph morphisms
$\usepackage[all]{xy} \xymatrix{ G_0\ar[d]_{\gamma_0} & X \ar[l]_{\partial_0}\ar[d]_{\gamma_0}\ar[r]^{\partial _1}&G_1\ar[d]_{\gamma_0}\\ A & G\ar[l]_{\partial_0} \ar[r]^{\partial_1}&B\\ G_2\ar[u] ^{\gamma_1}& Y\ar[l]_{\partial_0}\ar[u]^{\gamma_1}\ar[r]^{\partial _1}&G_3\ar[u]^{\gamma_1}}%$

We denote such a system very briefly as $G_{Y;A,B}^{X}$, or even $G_{Y}^{X}$
or $G_{A,B}$ or even just $G$, depending on the context.

Labels: , ,