Paper announcement

[Peter Selinger <selinger@math.lsa.umich.edu>]

Dear Category Theorists,

I am pleased to announce the availability of a new paper,

	Categorical Structure of Asynchrony,

available via http://www.math.lsa.umich.edu/~selinger/papers.html.

In this paper, I investigate properties of traced monoidal categories
that are satisfied by networks of asynchronously communicating
processes. Among these properties are Hasegawa's uniformity principle,
as well as a version of Kahn's principle: the subcategory of
*deterministic* processes is equivalent to a category of domains.

The paper also contains the following observation, which may be of
interest to categorists. I do not know whether this was observed
before, and would be grateful for references. Suppose T:Set-->Set is a
functor which is lax for the symmetric monoidal structure given by
products on the category of sets. Then T associates to any category C
another category C', which Benabou called the "direct image of C by
T". This category is defined as follows:

 obj(C') = obj(C),   and  C'(X,Y) = T(C(X,Y)).

The observation is that direct images preserve linear structure. More
precisely, if the category C possesses some algebraic structure which
is given by linear equations, then C' inherits that structure.
Non-linear structure is not in general preserved, although one can
give conditions on T under which the construction will preserve, for
instance, affine structure. One can also loosen the conditions on T,
so that it will only preserve non-commutative linear structure.

One can use the direct image construction to extract the linear "part"
of an arbitrary algebraic structure: for instance, if C has finite
products, then C' has a monoidal structure with diagonals, which is
precisely the part of a finite product structure which is given by
linear equations.

Traced monoidal structure with diagonals is the linear part of finite
product structure with fixpoints. One direction of this, namely that
the latter structure is a special case of the former, was observed by
Hasegawa and by Hyland, but I don't know whether it had been noticed
that the former is precisely the linear part of the latter.

An example of a non-commutative linear structure (given by linear
equations where the variables occur in the same left-to-right order on
both sides) is the premonoidal structure of Power and Robinson. This
is precisely the non-commutative part of monoidal structure. 

More details and examples are in the paper. Comments are, as usual,
welcome. Best wishes, -- Peter Selinger

----------------------------------------------------------------------
ABSTRACT:

We investigate a categorical framework for the semantics of
asynchronous communication in networks of parallel processes.
Abstracting from a category of asynchronous labeled transition
systems, we formulate the notion of a categorical model of asynchrony
as a uniformly traced monoidal category with diagonals, such that
every morphism is total and the focus is equivalent to a category of
complete partial orders. We present a simple, non-deterministic,
cpo-based model that satisfies these requirements, and we discuss how
to refine this model by an observational congruence. We also present a
general construction of passing from deterministic to
non-deterministic models, and more generally, from non-linear to
linear structure on a category.