R. ROSEBRUGHSABADINI, NICOLETTAWALTERS, ROBERT FRANK CARSLAWmostra contributor esterni nascondi contributor esterni 

GENERIC COMMUTATIVE SEPARABLE ALGEBRAS AND COSPANS OF GRAPHS

R. ROSEBRUGH, N. SABADINI AND R. F. C. WALTERS

Abstract. We show that the generic symmetric monoidal category with a commu- tative separable algebra which has a Σ-family of actions is the category of cospans of finite Σ-labelled graphs restricted to finite sets as objects, thus providing a syntax for automata on the alphabet Σ. We use this result to produce semantic functors for Σ- automata.

1. Introduction.

A variety of authors have considered (bi-)categories of cospans (and spans) of graphs in the study of algebras of processes. The present authors have concentrated attention on algebras of automata (in [11] , [12], [13], [20], [23]), cospan operations providing the sequential operations, and span operations corresponding parallel operations. In another direction, cospans have been used in pushout descriptions of graph rewriting in [7], [8], [24].

This paper concerns principally the first point of view, and in particular the sequential operations, though results similar to ours are already reported in [7], [8], for application to rewriting. It is our intention to study the parallel operations and distributive laws already introduced in [23] in a later paper.

The aim of this paper is to provide a complete syntax for cospans of labelled graphs, and at the same time provide a method for constructing semantic functors. These two things are accomplished by showing that the category of cospans of labelled graphs is initial in a certain context. Consider the category Csp(Graph

/Σ) whose objects are finite cardinals, regarded as discrete graphs, and whose arrows are cospans of graphs labelled by the alphabet Σ. This category has a symmetric strict monoidal structure supplied by the disjoint sum of sets, and a commutative separable algebra structure on the one element set 1, supplied by the codiagonal (cospan) ∇ : 1 + 1 ^// 1, the function ! : 0 ^// 1, and their opposite cospans ∆ : 1 ^// 1 + 1, ¡ : 1 ^// 0. In addition, for each letter of the alphabet Σ there is a cospan 1 ^// 1 (the center of the cospan consists of a two vertices and a single arc labelled by the letter). Our main theorem is that Csp(Graph

/Σ) is the initial such structure in the category of symmetric strict monoidal categories and symmetric strict monoidal functors.

The first part of the proof consists in identifying the initial strict monoidal category with a separable algebra as cospans of finite sets. When we announced that result at the

Received by the editors 2005-01-30 and, in revised form, 2005-10-09.

Published on 2005-10-12 in the volume of articles from CT2004.

2000 Mathematics Subject Classification: 18B20, 18D10, 68Q05, 68Q85.

Key words and phrases: separable algebra, cospan category.

 R. Rosebrugh, N. Sabadini and R. F. C. Walters , 2005. Permission to copy for private use granted. c

164

Vancouver conference [21] we discovered that Lack, as part of work on composing PROPs using distributive laws, now published in [17], had announced the same result. We show that freely adjoining Σ arrows 1 ^// 1 results in Csp(Graph

/Σ).

Perhaps some history is in order to make connections with other developments. In 1967 [16] Lawvere identified Frobenius algebras [15] as vector spaces with a multiplication

∇ and a comultiplication ∆ (and unit ! and counit ¡) satisfying

(1 ⊗ ¡)(∇ ⊗ 1)(1 ⊗ ∆) = ∇ = (¡ ⊗ 1)(1 ⊗ ∇)(∆ ⊗ 1), ( ∇ ⊗ 1)(1 ⊗ ∆)(! ⊗ 1) = ∆ = (1 ⊗ ∇)(∆ ⊗ 1)(1⊗!).

Independently Carboni and Walters [4] in characterizing the category of relations of a regular category discovered the equivalent axioms

(1 ⊗ ∇)(∆ ⊗ 1) = ∆∇ = (∇ ⊗ 1)(1 ⊗ ∆). (D) Following that work they developed a theory of symmetric monoidal categories with a well-supported self-dual compact closed structure [5], [25], in which the following axiom was identified

∇∆ = 1. (U)

In fact, well-supported compact closed amounts to requiring these last two axioms. At the Louvain conference Andr´ e Joyal pointed out that (D) is an axiom characteristic of 2-cobordisms. In 1991 Abrams [1] published a proof that the free symmetric monoidal category with a Frobenius algebra object is the category 2-Cobord. (Whether there is a line from Joyal’s remark to Abrams’ paper we do not know.) This result has also been referred to in the literature as “folklore”. A readable presentation appears in the monograph of J. Kock [15] devoted to this theorem. In this context it can be seen that axiom (U) expresses the condition “no holes”, and hence this suggests strongly that adding this axiom reduces 2-Cobord to Cospan(Sets

). Objects with a monoid and comonoid structure satisfying (D) and (U) in the category of finite dimensional vector spaces were identified by Carboni [5], following [6], as separable algebras.

2. Commutative separable algebra objects

2.1. Definition. We are concerned with strictly associative monoidal categories C, i.e.

monoids in Cat with multiplication and unit denoted

⊗ : C × C ^// C, I : 1 ^// C which are also symmetric, i.e. have the structure of a symmetry

τ

: C ⊗ D ^// D ⊗ C

natural in C and D and satisfying τ

τ

= 1

, and the equations:

τ

= (1

⊗ τ

)(τ

⊗ 1

) : X ⊗ Y ⊗ Z ^// Y ⊗ Z ⊗ X, τ

= (τ

⊗ 1

)(1

⊗ τ

) : X ⊗ Y ⊗ Z ^// Z ⊗ X ⊗ Y.

2.2. Example. The category denoted S

has natural numbers m, n, . . . as objects (and for notation, m is {0, 1, . . . , m − 1}), arrows from m to n are arbitrary functions. Indeed, S

is equivalent to the category of finite sets. The (strict!) monoidal tensor is denoted +, the “ordinal sum” on objects, that is m + n = {0, . . . , m + n − 1}. This extends in the obvious way to arrows. The unit for the tensor is the object 0. Further, with the symmetry τ

: m + n ^// n + m being the obvious permutation, S

is a symmetric strict monoidal category.

2.3. Example. The category denoted P has natural numbers as objects and permutations as arrows. The tensor is +, and the symmetry is as for S

. This category is the free symmetric strict monoidal category on an object, a result essentially due to E.H. Moore [18]. That is, for any symmetric strict monoidal category A, there is a bijection between symmetric strict monoidal functors F : P ^// A and objects of A, given by F −→ F (1).

Hence, for any permutation π of n and object A of a symmetric strict monoidal category A we may associate an automorphism of A ⊗ A ⊗ A ⊗ · · · ⊗ A (n fold) which we also denote, by abuse of notation, as π; in this way there is a homomorphism from the symmetric group on n letters to the automorphism group of A ⊗ A ⊗ A ⊗ · · · ⊗ A.

2.4. Example. The category Cospan(Sets

) has the same objects as S

. An arrow from m to n is an equivalence class of pairs of arrows (f, g) = m

^// p ^oo

n where the latter pair is equivalent to (f

, g

) = m

^// p

^oo

n exactly if there is a bijection h : p ^// p

such that hf = f

and hg = g

. We will denote the cospan (f, g), or more precisely its equivalence class, also as (f, g) : m
n to distinguish clearly between arrows in Cospan(Sets

) and those in Sets

. Composition is pushout, and is associative for equivalence classes. The monoidal structure, denoted +, is the same as for S

on objects and extends in the obvious way to arrows. The unit for the tensor is the object 0. Again there is obvious symmetric structure.

2.5. Example. Our principal example is Csp(Graph

/Σ): objects are again natural numbers m, n, . . ., arrows m
n are isomorphism classes of cospans of Σ-labelled finite graphs where a cospan of labelled finite graphs from m to n is a labelled finite graph G in S

and two functions

(γ

, γ

) = m

^// vert(G) ^oo

n Composition is pushout.

An isomorphism from this cospan to another

(γ

, γ

) = m

^// vert(H) ^oo

n

is a labelled graph isomorphism v : G ^// H such that vγ

= γ

, vγ

= γ

Of course, since they are isomorphic objects of S

, we actually have vert(G) = vert(H), and similarly for the edges of G and H. The monoidal structure, denoted +, is again as in S

on objects, with the obvious extension to arrows. The unit is 0. The symmetric structure is obvious.

2.6. Example. The last two examples are special cases of the fact that if C is a category with finite colimits then Cospan(C) is a symmetric monoidal category. A full subcat- egory, restricted to objects closed under sum, and for which the sum may be chosen as strictly associative, yields a symmetric strict monoidal category. For example, Cospan(V- Cat) for a cocomplete symmetric monoidal category V is symmetric monoidal, and if we restrict the objects to be natural numbers, considered as discrete V-categories, we obtain symmetric strict monoidal categories Csp(V-Cat). We will be interested in the special cases V = 2, Sets and ℘(Σ

), the power set of the free monoid on Σ.

2.7. Definition. A commutative separable algebra in a symmetric monoidal category is an object A equipped with four arrows

! : I ^// A,  : A ⊗ A ^// A, ∆ : A ^// A ⊗ A, ¡ : A ^// I

such that (A, ∇, !) form a commutative monoid, (A, ∆,¡) form a commutative comonoid and the following three axioms hold:

(1

⊗ ∇)(∆ ⊗ 1

) = ∆ ∇ = (∇ ⊗ 1

)(1

⊗ ∆) : A ⊗ A ^// A ⊗ A, (D)

∇∆ = 1

. (U)

We will denote the algebra as (A, !, ∇, ∆,¡ ) or, when there is no confusion, simply as A.

Note. These axioms are highly redundant. For example, clearly only one of the axioms (D) is needed, the associative laws for the (co-)monoid structure are deducible, and so on, see [15].

2.8. Proposition. If every object A of a symmetric monoidal category A has a commu- tative separable algebra structure !

, ∇

, ∆

,¡

then A is self-dual compact closed.

Proof. ([4]) Define η

to be ∆

!

: I ^// A ^// A ⊗ A, and ε

to be ¡

∇

: A ⊗ A ^// A ^// I. We have only two equations to check, namely that (ε

⊗ 1

)(1

⊗ η

) = 1

and (1

⊗ ε

)(η

⊗ 1

) = 1

. But

(ε

⊗ 1

)(1

⊗ η

) = (¡

∇

⊗ 1

)(1

⊗ ∆

!

)

= (¡

⊗ 1

)( ∇

⊗ 1

)(1

⊗ ∆

)(1

⊗!

)

= (¡

⊗ 1

)∆

∇

(1

⊗!

)

= 1

.

The proof of the second equation is similar.

2.9. Definition. A symmetric monoidal category in which every object has a commuta- tive separable algebra structure is called well-supported compact closed(wscc).

Note. From the fact that self-dual compact closed amounts to the requirement that each object A is adjoint to itself, and from general facts about adjoints, a compact closed structure on a symmetric monoidal category is essentially unique. We note that Carboni [5] also requires a compatibility condition between the monoidal and separable structures in a well-supported compact closed category. However, a wscc category as defined here is equivalent to one with his compatibility condition.

2.10. Proposition. If objects A and B of symmetric monoidal category A admit commu- tative separable algebra structures then so does A ⊗ B. As a consequence, if all the objects of a symmetric monoidal category are tensor powers of a single commutative separable algebra, the category is well-supported compact closed.

Proof. The following arrows furnish a commutative separable algebra structure for A ⊗B:

!

=!

⊗!

: I ^// A ⊗ B,



= ( ∇

⊗ ∇

)(1

⊗ τ

⊗ 1

) : A ⊗ B ⊗ A ⊗ B ^// A ⊗ B,

∆

= (1

⊗ τ

⊗ 1

)(∆

⊗ ∆

) : A ⊗ B ^// A ⊗ B ⊗ A ⊗ B,

¡

= ¡

⊗ ¡

: A ⊗ B ^// I.

Checking the equations is straightforward.

2.11. Example. If C is a category with finite colimits then Cospan(C) is well-supported compact closed – the commutative separable algebra structure on object A is provided by unit ! = (!, 1

) : 0
A, multiplication ∇ = (∇

, 1

) : A + A
A, comultiplication

∆ = (1

, ∇

) : A
A + A, and counit ¡ = (1

, ! ) : A
0. Notice we have overloaded the symbols by using them for the appropriate operations in C and also Cospan(C). As a consequence Cospan(Sets

), Csp(Graph

/Σ) and Csp(V-Cat) are well-supported compact closed.

2.12. Definition. A commutative separable algebra with a Σ-family of actions in a symmetric monoidal category is a commutative separable algebra A together with a family of arrows (α

: A ^// A)

. Notice that the arrows are not required to preserve any operations.

2.13. Example. In both Csp(Graph

/Σ) and Csp(℘(Σ

)-Cat) the object 1, as well

as being a commutative separable algebra as noted above, has a Σ-family of actions. In

Csp(Graph

/Σ) the cospan α

= (∂

, ∂

) corresponding to σΣ has as middle graph

two vertices 0, 1 with a single edge 0 ^// 1 labelled by σ; the image of ∂

is 0, and of ∂

is 1. In Csp(℘(Σ

)-Cat) the cospan α

corresponding to σΣ has as middle category two

objects 0, 1 with the only non-trivial homset being hom(0, 1) = {σ}.

3. The syntax of cospans of graphs

3.1. Proposition. [17], [21] The object 1 with structure (1, !

, ∇

, ∆

,¡

) in the category Cospan(Sets

) is the generic commutative separable algebra in the category of sym- metric strict monoidal categories and symmetric strict monoidal functors. That is, for each symmetric strict monoidal category A there is a bijection between symmetric strict monoidal functors Φ : Cospan(Sets

) ^// A and commutative separable algebras A in A, given by the assignment Φ −→ (Φ(1), Φ(!

), Φ( ∇

), Φ(∆

), Φ(¡

)).

Note. As we have remarked in the example above, any object of Cospan(Sets

), and hence in particular 1, has a commutative separable algebra structure, and such a structure is clearly preserved by a symmetric strict monoidal functor. Lack’s proof [17]

of the proposition uses a decomposition of the notion of commutative separable algebra, into other algebraic structures connected by rewrite laws (traditionally called distributive laws [2]), just as the notion of ring may be decomposed into monoid plus abelian group connected by a distributive law. This decomposition works also at the level of theories [22]. The most interesting aspect is that the axioms (D) and (U), considered as rewrite laws compute the pushout up to isomorphism of functions between finite sets. Notice that the result should not be confused with that of Gates [9] which deals with generic separable objects in extensive categories, where separable has a different meaning.

The main result of this paper is the following:

3.2. Proposition. The object 1 with structure (1, !

, ∇

, ∆

,¡

, (α

)

) in the category Csp(Graph

/Σ) is the generic commutative separable algebra with a Σ-family of actions in the category of symmetric strict monoidal categories and symmetric strict monoidal functors. That is, for each symmetric strict monoidal category A there is a bijection be- tween symmetric strict monoidal functors Ψ : Csp(Graph

/Σ) ^// A and commutative separable algebras A with a Σ-family of actions, in A, given by the assignment

Ψ → (Ψ(!

), Ψ( ∇

), Ψ(∆

), Ψ(¡

), (Ψ(α

))

).

For simplicity we will prove this result in the special case Σ = 1, that is, in the unla- belled case Csp(Graph

). For this we need a normal form for arrows in Csp(Graph

), provided in the following proposition.

3.3. Proposition. Any cospan (γ

, γ

) : m ^// G ^oo n in Csp(Graph

) may be written in the form

m ^// G ^oo n ∼ = (1

+ ε

)(φ + ( +

eE

α

))(1

+ η

). (NF) where E is the edge set of G, V is the vertex set, the source and target functions of G are d

, d

, and

φ = ((γ

|d

), (γ

|d

)) : m + E ^// V ^oo n + E is the cospan of sets induced by the γ’s and d’s. Note that +

eE

α

is a cospan E
E, and

η

: 0
E + E, ε

: E + E
0 are unit and counit of the compact closed structure on

cospans of sets.

The expression (NF) is unique in the following sense. Whenever m ^// G ^oo n ∼ = (1

+ ε

)(ψ + ( +

eE

α

))(1

+ η

) it is the case that

ψ = (1

+ π)φ(1

+ π

)

where π is a cospan of the form π = (π

, 1

) : E
E with π

: E ^// E a bijection.

3.4. Remark. It is useful to have pictures in doing calculations in compact closed cat- egories. The reader may be interested to view calculations aided by pictures in traced monoidal categories [10] which are valid also for compact closed categories. The picture we have in mind for normal forms is as follows:

φ

- -

m n

eE

+ α

η

ε

Proof of Proposition 3.3. The crucial (double) pushout to calculate in Graph

is of the diagram

E ^oo

E + E

^// V + ( +

eE

α

) ^oo

E + E

^// E, where r = d

+ ( +

eE

∂

) and s = d

+ ( +

eE

∂

). The result is V + ( +

eE

α

) quotiented by the relation that the first vertex of α

must be d

(e), and the second d

(e). That is, the graph G is constructed by taking E disjoint arrows, and V additional vertices, and equating the sources and targets of the disjoint arrows according to the functions d

, d

.

Regarding the uniqueness, suppose (1

+ ε

)(φ

+ ( +

eE

α

))(1

+ η

) is an expression which evaluates to (γ

, γ

) : m ^// G

^oo n, a cospan isomorphic to m ^// G ^oo n. Then φ

= ((γ

|d

), (γ

|d

)) where d

, d

are the source and target of G

. There exist bijections π

: V ^// V, π

: E ^// E such that π

d

= d

π

, π

d

= d

π

and π

γ

= γ

, π

γ

= γ

. These equations are exactly what is required to verify that φ

∼ = (1

+ π)φ(1

+ π

), noting that the inverse cospan to (π

, 1

) : E
E in Csp(Graph

) is (1

, π

)).

Proof of Proposition 3.2. (unlabelled case) First notice that there is an inclusion Cospan(Sets

) ^// Csp(Graph

)

which preserves the object 1 and its structure (1, !

, ∇

, ∆

,¡

) as a commutative sep-

arable algebra – just regard a set as a graph with vertices but no edges. Consider

A = (A, !

, ∇

, ∆

,¡

, α

), a commutative separable algebra with an action, in A. By Proposition 3.1 there is a unique functor Φ : Cospan(Sets

) ^// A such that

(Φ(1), Φ(!

), Φ( ∇

), Φ(∆

), Φ(¡

)) = (A, !

, ∇

, ∆

, ¡

).

We need to show that Φ extends uniquely to a functor Ψ : Csp(Graph

) ^// A such that Ψ(α

) = α

.

Uniqueness: To show that there is at most one extension Ψ of Φ it is sufficient to show that any cospan (γ

, γ

) = m ^// G ^oo n of labelled graphs may be given by an expression involving composition, tensor +, symmetry τ , cospans of finite sets, and the actions α

. But this is provided by the normal form.

Existence: We define Ψ using the normal forms of cospans of graphs. If cospan (γ

, γ

) = m ^// G ^oo n has normal form (1

+ ε

)((φ + ( +

eE

α

))(1

+ η

) then we define Ψ(m ^// G ^oo n) by

Ψ(m ^// G ^oo n) = (Φ(1

) ⊗ Φ(ε

))((Φ(φ) ⊗ ( ⊗

eE

α

))(Φ(1

) ⊗ Φ(η

)) ∈ A.

We need to check that Ψ is well-defined, and then that Ψ is functorial and monoidal.

We suspend our proof of Proposition 3.2 to consider three general lemmas concerning self-dual compact closed categories. Then well-definedness will follow from Lemma 3.5, functoriality from Lemma 3.6, and monoidality from Lemma 3.7. In fact we will prove just the first of the three lemmas in detail leaving the others to the reader.

3.5. Lemma. Let X, A be objects of a self-dual compact closed category. Consider P =

iI

⊗ A, and consider arrows α : A ^// A, φ : X ⊗ P ^// X ⊗ P , and a permutation π : P ^// P. Then

(1

⊗ ε

)((1

⊗ π)φ(1

⊗ π

) ⊗ (⊗

iI

α))(1

⊗ η

)

= (1

⊗ ε

)(φ ⊗ (⊗

iI

α))(1

⊗ η

). (1) Picture of the statement of Lemma 3.5

φ ^-

π

π

⊗α

φ

⊗α

-

Proof of Lemma 3.5. It is easy to check, using naturality of τ and the compact closed property, that (τ

⊗ 1

)η

= (1

⊗ τ

)η

. A consequence is that if P = ⊗

iI

A and π : P ^// P is a permutation then

(π

⊗ 1

)η

= (1 ⊗ π

)η

.

A similar property holds for ε

. Then

Left hand side of (1) = (1

⊗ (ε

(π

⊗ 1

)))(φ ⊗ (⊗

iI

α))(1

⊗ ((π

⊗ 1

)η

))

= (1

⊗ (ε

(1

⊗ π

)))(φ ⊗ (⊗

iI

α))(1

⊗ ((1

⊗ π

)η

)) (by the above remark)

= (1

⊗ ε

)(φ ⊗ π

( ⊗

iI

α)π)(1

⊗ η

)

= (1

⊗ ε

)(φ ⊗ π

π( ⊗

iI

α))(1

⊗ η

) (by naturality of τ )

= (1

⊗ ε

)(φ ⊗ (⊗

iI

α))(1

⊗ η

).

3.6. Lemma. [Composite of normal forms] Let X, Y, Z, A be objects of a self-dual compact closed category. Consider P = ⊗

iI

A, Q = ⊗

jJ

A, and consider arrows α : A ^// A, φ : X ⊗ P ^// Y ⊗ P , ψ : Y ⊗ Q ^// Z ⊗ Q. Then

[(1

⊗ ε

)(ψ ⊗ ( ⊗

jJ

α))(1

⊗ η

)][(1

⊗ ε

)(φ ⊗ (⊗

iI

α))(1

⊗ η

)]

= (1

⊗ ε

)(θ ⊗ ( ⊗

kI+J

α))(1

⊗ η

), where θ = (1

⊗ τ

)(ψ ⊗ 1

)(1

⊗ τ

)(φ ⊗ 1

).

Picture of the statement of Lemma 3.6

φ ψ

⊗

α ⊗

α

- φ ψ ^-

⊗

α

3.7. Lemma. [Tensor of normal forms] Let X, Y, Z, W, A be objects of a self-dual compact closed category. Consider P = ⊗

iI

A, Q = ⊗

jJ

A, and consider arrows α : A ^// A, φ : X ⊗ P ^// Y ⊗ P , ψ : Z ⊗ Q ^// W ⊗ Q. Then

[(1

⊗ ε

)(φ ⊗ (⊗

iI

α))(1

⊗ η

)] ⊗ [(1

⊗ ε

)(ψ ⊗ ( ⊗

jJ

α))(1

⊗ η

)]

= (1

⊗ ε

)(θ ⊗ ( ⊗

kI+J

α))(1

⊗ η

),

where θ = (1

⊗ τ

⊗ 1

)(φ ⊗ ψ)(1

⊗ τ

⊗ 1

).

Picture of the statement of Lemma 3.7

φ

⊗

α ψ

⊗

α

-

-

φ ψ

⊗

α

- -

Proofs of Lemmas 3.6 and 3.7 are straightforward calculations in a self-dual compact closed category.

Completing the proof of Proposition 3.2.

Recall that Φ preserves the separable algebra structure of 1 and hence the com- pact closed structure of Cospan(Sets

) (which is also the compact closed structure of Csp(Graph

)). The ambiguity in the definition of Ψ arises from the ambiguity of nor- mal forms described in Proposition 3.3, but this ambiguity is exactly resolved by Lemma 3.5.

For the two points remaining, functoriality and monoidality, we prove only the first since the style of proof for second is the same. Consider two cospans S, S

of graphs with normal forms

(1

+ ε

)(φ + ( +

eE

α

))(1

+ η

), (1

+ ε

)(φ

+ ( +

eE

α

))(1

+ η

), respectively. By Lemma 3.6 in the category Csp(Graph

), the composite S

S is

(1

+ ε

)((1

+ τ

)(φ

+ 1

)(1

+ τ

)(φ + 1

) + ( +

eE+E

α

))(1

+ η

).

But

Ψ(S

S) =

(Φ(1

) ⊗ Φ(ε

))(Φ {(1

⊗ τ

)(φ

⊗ 1

)(1

⊗ τ

)(φ ⊗ 1

) }⊗

⊗ ( ⊗

eE+E

α

))(Φ(1

) ⊗ Φ(η

))

= (1

⊗ ε

)((1

⊗ τ

)(Φ(φ

) ⊗ 1

)(1

⊗ τ

) (Φ(φ) ⊗ 1

) ⊗ ⊗( ⊗

eE+E

α

))(1

⊗ η

)

= Ψ(S

)Ψ(S),

this last, by Lemma 3.6 applied in the category A.

4. Semantic functors

Semantic functors are structure-preserving functors out of Csp(Graph

/Σ) into suitable categories. We have discussed the construction of such functors in the context of automata in [14], and would like to look at some examples suggested by Proposition 3.2. Clearly this proposition suggests looking for symmetric monoidal categories with commutative separable algebra objects, or even well-supported compact closed categories, as codomains for semantic functors.

4.1. Example. Csp(Cat) contains a commutative separable algebra 1 together with a specific cospan 1

^// 2 ^oo

1 whose middle category is the ordered set 2 = {0 ≤ 1}.

The image of ∂

is 0 and of ∂

is 1. This structure in Csp(Cat) induces, by Proposition 3.2 a strict monoidal functor

Ψ : Csp(Graph

) ^// Csp(Cat).

But this functor may be identified in another way. The free category construction F (on a graph) preserves pushouts and sums, and hence induces a strict monoidal functor

Csp(F) : Csp(Graph

) ^// Csp(Cat),

which also takes the generic commutative separable algebra and its action to 1 together with the cospan 1

^// 2 ^oo

1. Hence Ψ = F. The intuition that this is a semantic functor comes from the fact that paths in a graph form the arrows in the free category on the graph. This is related to the idea in [19] that behaviours in a place-transition Petri net consist of arrows in the free monoidal category generated by the net. If we compose F with

Csp(Π

) : Csp(Cat) ^// Csp(S

),

where Π

is the connected components functor, we obtain a behaviour closely related to the classical partial function behaviour [12], in which the duration of a computation is collapsed to zero.

4.2. Example. Csp(℘(Σ

)-Cat) contains a commutative separable algebra 1 together with a Σ family of cospans 1

^// α

^oo

1 (σΣ) with α

having two objects 0, 1 and non-trivial homset hom(0, 1) = {σ}. This structure in Csp(℘(Σ

)-Cat) induces, by Proposition 3.2 a strict monoidal functor

Ψ : Csp(Graph

/Σ) ^// Csp(℘(Σ

)-Cat).

This functor may be identified in another way. The free ℘(Σ

) category construction (on a ℘(Σ

) graph [3]) preserves pushouts and sums, and hence induces a strict monoidal functor

Csp(Graph

/Σ) ^// Csp(℘(Σ

)-Cat),

which also takes the generic commutative separable algebra and its actions to 1 together with the cospans α

, and hence this is the functor Ψ. The intuition that this is a semantic functor comes from the fact behaviours in a labelled graph are languages traced out by paths in the graph. In [12] we described a different behaviour, in a slightly different context, where the codomain category was the (non-self-dual) compact closed category Int(Matr(℘(Σ

)), the Int construction [10] applied to matrices of languages. To make a comparison between the two notions of behaviour it may be useful to notice that a cospan m ^// C ^oo n in Csp(℘(Σ

)) induces a functor m + n ^// C which may be factorized into two functors, a bijective-on-objects m + n ^// C

and a fully faithful C

^// C, the first of which might be considered a more precise notion of behaviour. Instead, an m × n matrix of languages may be construed as a bijective-on-objects functor from m + n to the rather special ℘(Σ

)-category whose (non-trivial) homs are the entries of the matrix. The role in composition of pushout in Csp(℘(Σ

)) is taken by trace in Int(Matr(℘(Σ

)).

4.3. Remark. The intuition guiding this paper is that the actions (α

)

are basic processes out of which composite processes are produced by the operations of a separable algebra, and the monoidal category operations. In a future paper we will study the situation in which the basic processes are typed, and also in which there are parallel operations on basic operations which extend to composite processes via distributive laws like those in [23] (just as product operations on polynomials arise by distributive laws from products of monomials).

References

[1] L. Abrams, Two dimensional topological quantum field theories and Frobenius alge- bras, J. Knot Theory Ramifications, 5, 569–587, 1996.

[2] J. Beck, Distributive laws, in Seminar on Triples and Categorical Homology Theory, Lecture Notes in Mathematics, 80, pages 119–140, Springer-Verlag, 1969.

[3] R. Betti, A. Carboni, R.H. Street and R.F.C. Walters, Variation through enrichment, Journal of Pure and Applied Algebra, 29, 109–127, 1983.

[4] A. Carboni, R.F.C. Walters, Cartesian Bicategories I, J. Pure Applied Algebra, 49, 11–32, 1987.

[5] A. Carboni, Matrices, relations and group representations, J. Algebra, 138, 497–529, 1991.

[6] F. DeMeyer, E. Ingraham, Separable algebra over commutative rings, Springer Lec- ture Notes in Mathematics, 181, 1971.

[7] F. Gadducci, R. Heckel, An inductive view of graph transformation, Springer LNCS,

1376, 223–237, 1997.

[8] F. Gadducci, R. Heckel, M. Llabres, A bi-categorical axiomatisation of concurrent graph rewriting, ENTCS, 29, 1999.

[9] R. Gates, On generic separable objects, Theory and Applications of Categories, 4, 204–248, 1998.

[10] A. Joyal, R.H. Street, D. Verity, Traced monoidal categories, Math. Proc. Cambridge Philosophical Soc. 119 (3), 425–446, 1996.

[11] P. Katis, N. Sabadini, R.F.C. Walters, Span(Graph): A categorical algebra of tran- sition systems, Proc. AMAST ’97, SLNCS 1349, 307–321, Springer Verlag, 1997.

[12] P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback and boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63, 123–156, 2000.

[13] P. Katis, N. Sabadini, R.F.C. Walters, A formalisation of the IWIM Model, in:

Proc. COORDINATION 2000, (Eds.) A. Porto, G.-C. Roman, LNCS 1906, 267–

283, Springer Verlag, 2000.

[14] P. Katis, N. Sabadini, R.F.C. Walters, Feedback, trace and fixed-point semantics, Theoret. Informatics Appl. 36, 181–194, 2002.

[15] J. Kock, Frobenius algebras and 2D topological Quantum Field Theories, Cambridge University Press, 2004.

[16] F. W. Lawvere, Ordinal sums and equational doctrines, Springer Lecture Notes in Mathematics, 80, 141–155, 1967.

[17] S. Lack, Composing PROPs, Theory and Applications of Categories, 13, 147–163, 2004.

[18] E.H. Moore, Concerning the abstract group of order k! and

k!, Proc. London Math.

Soc, 28, 357–366, 1897.

[19] J. Meseguer, U. Montanari, Petri Nets are Monoids, Information and Computation, 88, 105–155, 1990. Also SRI-CSL-88-3, January 1988.

[20] R. Rosebrugh, N. Sabadini, R.F.C. Walters, Minimization and minimal realization in Span(Graph), Mathematical Structures in Computer Science, 14, 685–714, 2004.

[21] R. Rosebrugh, N. Sabadini, R.F.C. Walters, Symmetric separable algebras in monoidal categories and Cospan(Graph), Abstracts of the International Category Theory Conference, CT’04, Vancouver 2004.

[22] R. Rosebrugh, R.J. Wood, Factorization Systems and Distributive Laws, J. Pure

Appl. Alg. 175, 327–353, 2002.

[23] N. Sabadini, R.F.C. Walters, Hierarchical automata and P systems, CATS’03, ENTCS 78, 2003.

[24] P. Sobocinski, Process congruences from reaction rules, in Luca Aceto’s “Concurrency Column”, Bulletin of the EATCS vol. 84, 2004.

[25] R.F.C. Walters, The tensor product of matrices, Lecture, International Conference on Category Theory, Louvain-la-Neuve, 1987.

Department of Mathematics and Computer Science Mount Allison University

Sackville, N. B. E4L 1E6 Canada

Dipartimento di Scienze della Cultura, Politiche, e dell’Informazione Universit` a dell’Insubria

via Valleggio, 11, 22100 Como, Italy

Dipartimento di Scienze della Cultura, Politiche, e dell’Informazione Universit` a dell’Insubria

via Valleggio, 11, 22100 Como, Italy and

School of Mathematics and Statistics University of Sydney

Sydney, NSW 2006, Australia Email: rrosebrugh@mta.ca

nicoletta.sabadini@uninsubria.it robert.walters@uninsubria.it

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/15/6/15-06.{dvi,ps}

tions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor.

Information for authors. The typesetting language of the journal is TEX, and L

TEX 2ε is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Universit´ e d’ Ottawa: rblute@mathstat.uottawa.ca Lawrence Breen, Universit´ e de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Universit` a dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk

P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk

Stephen Lack, University of Western Sydney: s.lack@uws.edu.au

F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Universit´ e de Strasbourg: loday@math.u-strasbg.fr

Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu

Robert Par´ e, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz

Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu

Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu

Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it

R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca