From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1188 Path: news.gmane.org!not-for-mail From: Peter Selinger Newsgroups: gmane.science.mathematics.categories Subject: Paper announcement Date: Sat, 31 Jul 1999 00:45:43 -0400 (EDT) Message-ID: <199907310445.AAA06766@blackbox.math.lsa.umich.edu> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241017624 29880 80.91.229.2 (29 Apr 2009 15:07:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:07:04 +0000 (UTC) To: categories@mta.ca (Categories List) Original-X-From: cat-dist Sat Jul 31 11:39:15 1999 Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA32002 for categories-list; Sat, 31 Jul 1999 10:41:19 -0300 (ADT) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Mailer: ELM [version 2.4 PL25] Original-Sender: cat-dist@mta.ca Precedence: bulk Original-Lines: 68 Xref: news.gmane.org gmane.science.mathematics.categories:1188 Archived-At: 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.