paper announcement

paper announcement

[Michael MAKKAI]

I am announcing a paper, and enclose an (somewhat) extended abstract. The
paper is available at the site

	ftp://ftp.math.mcgill.ca/pub/makkai ,

the name of the file is mltomcat.zip . It is a ZIPPED package of 8
POSTSCRIPT files. When accessed through NETSCAPE, there was no difficulty
getting it; but with ordinary ftp-ing, we couldn't get to it. The problems
with the ftp sites here at McGill are being looked at, but they are not
solved yet.




	The multitopic omega-category of all multitopic omega-categories

			by M. Makkai (McGill University)

				September 2, 1999


Abstract

The paper gives two definitions: that of "multitopic omega-category" and
that of "the (large) multitopic set of all (small) multitopic
omega-categories". It also announces the theorem that the latter is a
multitopic omega-category. (The proof of the theorem will be contained in
a sequel to this paper.)

The work has two direct sources. One is the paper [H/M/P] (for the
references, see at the end of this abstract) in which, among others, the
concept of "multitopic set" was introduced. The other is the present
author's work on FOLDS, First Order Logic with Dependent Sorts. The
latter was reported on in [M2]. A detailed account of the work on FOLDS is
in [M3]. For the understanding of the present paper, what is contained in
[M2] suffices. In fact, section 1 of the present paper gives the
definitions of all that's needed in this paper; so, probably, there won't
be even a need to consult [M2]. 

The concept of multitopic set, the main contribution of [H/M/P], was, in
turn, inspired by the work of J. Baez and J. Dolan [B/D]. Multitopic sets
are a variant of opetopic sets of loc. cit. The name "multitopic set"
refers to multicategories, a concept originally due to J. Lambek [L], and
given an only moderately generalized formulation in [H/M/P]. The earlier
"opetopic set" of [B/D] is based on a concept of operad. I should say that
the exact relationship of the two concepts ("multitopic set" and "opetopic
set") is still not clarified. The main aspect in which the theory of
multitopic sets is in a more advanced state than that of opetopic sets is
that, in [H/M/P], there is an explicitly defined category Mlt of
*multitopes*, with the property that the category of multitopic sets is
equivalent to the category of Set-valued functors on Mlt, a result given a
detailed proof in [H/M/P]. The corresponding statement on opetopic sets
and opetopes is asserted in [B/D], but the category of opetopes is not
described. In this paper, the category of multitopes plays a basic role.

Multitopic sets and multitopes are described in section 2 of this paper;
for a complete treatment, the paper [H/M/P] should be consulted.

The indebtedness of the present work to the work of Baez and Dolan goes
further than that of [H/M/P]. The second ingredient of the Baez/Dolan
definition, after "opetopic set", is the concept of "universal cell". The
Baez/Dolan definition of weak n-category achieves the remarkable feat of
specifying the composition structure by universal properties taking place
in an opetopic set. In particular, a (weak) opetopic (higher-dimensional)
category is an opetopic set with additional properties ( but with no
additional data), the main one of the additional properties being the
existence of sufficiently many universal cells. This is closely analogous
to the way concepts like "elementary topos" are specified by universal
properties: in our situation, "multitopic set" plays the "role of the
base" played by "category" in the definition of "elementary topos". In
[H/M/P], no universal cells are defined, although it was mentioned that
their definition could be supplied without much difficulty by imitating
[B/D]. In this paper, the "universal (composition) structure" is supplied
by using the concept of FOLDS-equivalence of [M2].

In [M2], the concepts of "FOLDS-signature" and "FOLDS-equivalence" are
introduced. A (FOLDS-) signature is a category with certain special
properties. For a signature L , an *L-structure* is a Set-valued functor
on L. To each signature L, a particular relation between two variable
L-structures, called L-equivalence, is defined. Two L-structures M, N, are
L-equivalent iff there is a so-called L-equivalence span M<---P--->N
between them; here, the arrows are ordinary natural trasnformations,
required to satisfy a certain property called "fiberwise surjectivity".

The slogan of the work [M2], [M3] on FOLDS is that *all meaningful
properties of L-structures are invariant under L-equivalence*. As with all
slogans, it is both a normative statement ("you should not look at
properties of L-structures that are not invariant under L-equivalence"),
and a statement of fact, namely that the "interesting" properties of
L-structures are in fact invariant under L-equivalence. (For some slogans,
the "statement of fact" may be false.) The usual concepts of "equivalence"
in category theory, including the higher dimensional ones such as
"biequivalence", are special cases of L-equivalence, upon suitable, and
natural, choices of the signature L; [M3] works out several examples of
this. Thus, in these cases, the slogan above becomes a tenet widely held
true by category theorists. I claim its validity in the generality stated
above.

The main effort in [M3] goes into specifying a language, First Order Logic
with Dependent Sorts, and showing that the first order properties
invariant under L-equivalence are precisely the ones that can be defined
in FOLDS. In this paper, the language of FOLDS plays no role. The concepts
of "FOLDS-signature" and "FOLDS-equivalence" are fully described in
section 1 of this paper. 

The definition of *multitopic omega-category* goes, in outline, as
follows. For an arbitrary multitope SIGMA of dimension >=2, for a
multitopic set S, for a pasting diagram ALPHA in S of shape the domain of
SIGMA and a cell a in S of the shape the codomain of SIGMA, such that a
and ALPHA are parallel, we define what it means to say that a is a
*composite* of ALPHA. First, we define an auxiliary FOLDS signature
L<SIGMA> extending Mlt, the signature of multitopic sets. Next, we define
structures S<a> and S<ALPHA>, both of the signature L<SIGMA>, the first
constructed from the data S and a , the second from S and ALPHA, both
structures extending S itself. We say that a is a composite of ALPHA if
there is a FOLDS-equivalence-span E between S<a> and S<ALPHA> that
restricts to the identity equivalence-span from S to S . Below, I'll refer
to  E as an *equipment* for  a  being a composite of ALPHA. A multitopic
set is a *mulitopic omega-category* iff every pasting diagram  ALPHA in it
has at least one composite.

The analog of the universal arrows in the Baez/Dolan style definition is
as follows. A *universal arrow* is defined to be an arrow of the form
b:ALPHA-----> a where  a  is a composite of ALPHA via an equipment E that
relates b with the identity arrow on  a : in turn, the identity arrow on
a  is any composite of the empty pasting diagram of dimension  dim(a)+1
based on  a . Note that the main definition does *not* go through first
defining "universal arrow". 

A new feature in the present treatment is that it aims directly at weak
*omega*-categories; the finite dimensional ones are obtained as truncated
versions of the full concept. The treatment in [B/D] concerns finite
dimensional weak categories. It is important to emphasize that a
multitopic omega category is still just a multitopic set with additional
properties, but with no extra data.

The definition of "multitopic omega-category" is given is section 5; it
uses sections 1, 2 and 4, but not section 3.

The second main thing done in this paper is the definition of MltOmegaCat.
This is a particular large multitopic set. Its definition is completed
only by the end of the paper. The 0-cells of MltOmegaCat are the samll
multitopic omega-categories, defined in section 5. Its 1-cells, which we
call 1-transfors (thereby borrowing, and altering the meaning of, a term
used by Sjoerd Crans [Cr]) are what stand for "morphisms", or "functors",
of multitopic omega-categories. For instance, in the 2-dimensional case,
multitopic 2-categories correspond to ordinary bicategories by a certain
process of "cleavage", and the 1-transfors correspond to homomorphisms of
bicategories [Be]. There are n-dimensional transfors for each n in N . For
each multitope (that is, "shape" of a higher dimensional cell) PI, we
have the *PI-transfors*, the cells of shape PI in MltOmegaCat.

For each fixed multitope PI, a PI-transfor is a *PI-colored multitopic
set* with additional properties. "PI-colored multitopic sets" are defined
in section 3; when PI is the unique zero-dimensional multitope, PI-colored
multitopic sets are the same as ordinary multitopic sets. Thus, the
definition of a transfor of an arbitrary dimension and shape is a
generalization of that of "multitopic omega-category"; the additional
properties are also similar, they being defined by FOLDS-based universal
properties. There is one new element though. For dim(PI)>=2 , the concept
of PI-transfor involves a universal property which is an
omega-dimensional, FOLDS-style generalization of the concept of right
Kan-extension (right lifting in the terminology used by Ross Street).
This is a "right-adjoint" type universal property, in contrast to the
"left-adjoint" type involved in the concept of composite (which is a
generalization of the usual tensor product in modules). 

The main theorem, stated but not proved here, is that  MltOmegaCat is a
multitopic omega-category. 

The material in this paper has been applied to give formulations of
omega-dimensional versions of various concepts of homotopy theory;
details will appear elesewhere.

I thank Victor Harnik and Marek Zawadowski for many stimulating
discussions and helpful suggestions. I thank the members of the Montreal
Category Seminar for their interest in the subject of this paper, which
made the exposition of the material at a time when it was still in an
unfinished state a very enjoyable and useful process for me.


References:

[B/D]	J. C. Baez and J. Dolan, Higher-dimensional algebra III.
n-categories and the algebra of opetopes. Advances in Mathematics 135
(1998), 145-206.

[Be]	J. Benabou, Introduction to bicategories. In: Lecture Notes in
Mathematics 47 (1967), 1-77 (Springer-Verlag). 

[Cr]	S. Crans, Localizations of transfors. Macquarie Mathematics
Reports no. 98/237. 

[H/M/P]	C. Hermida, M. Makkai and J. Power, On weak higher dimensional
categories I. Accepted by: Journal of Pure and Applied Algebra. Available
electronically (when the machines work ...).

[L]	J. Lambek, Deductive systems and categories II. Lecture Notes in
Mathematics 86 (1969), 76-122 (Springer-Verlag). 

[M2]	M. Makkai, Towards a categorical foundation of mathematics. In:
Logic Colloquium '95 (J. A. Makowski and E. V. Ravve, editors). Lecture
Notes in Logic 11 (1998) (Springer-Verlag). 

[M3]	M. Makkai, First Order Logic with Dependent Sorts. Research
momograph, accepted by Lecture Notes in Logic (Springer-Verlag). Under
revision. Original form available electronically (when the machines
work ...). 





Cheers: M. Makkai

Paper announcement

[Luca Cattani]

The following paper is available at

   http://www.cl.cam.ac.uk/~glc25/premcl.html   .

It will also be available soon as BRICS Report, RS-99-36 (see 
www.brics.dk/Publications), and as Cambridge University Computer Laboratory 
Technical Report n. 477 (contact tech-reports@cl.cam.ac.uk to obtain a hard 
copy) :

             Presheaf Models for CCS-like Languages    

        Gian Luca Cattani                   Glynn Winskel
       Computer Laboratory                      BRICS
     University of Cambridge            University of Aarhus
           England                             Denmark


Abstract
=========

The aim of this paper is to harness the mathematical machinery around 
presheaves for the purposes of process calculi. Joyal, Nielsen and Winskel 
proposed a general definition of bisimulation from open maps. Here we show 
that open-map bisimulations within a range of presheaf models are congruences 
for a general process language, in which CCS and related languages are easily 
encoded. The results are then transferred to traditional models for processes. 
By first establishing the congruence results for presheaf models, abstract, 
general proofs of congruence properties can be provided and the awkwardness 
caused through traditional models not always possessing the cartesian 
liftings, used in the break-down of process operations, are side-stepped. The 
abstract results are applied to show that hereditary history-preserving 
bisimulation is a congruence for CCS-like languages to which is added a 
refinement operator on event structures as proposed by van Glabbeek and Goltz.

paper announcement

[Fabio Gadducci]

Dear members of the mailing list, I'm pleased to annouce that the paper

        ``Rewriting on Cyclic Structures'',

by myself and Andrea Corradini, is available at
http://www.di.unipi.it/~gadducci/papers/RAIRO.ps.
The abstract follows, but shortly, it uses traced monoidal 2-categories
--where, in addition, each object ha`s a comonoidal structure-- in order
to simulate various kinds of (eventually cyclic) term (graph) rewriting.

Its interest for a broader audience may lie, besides in showing a
practical application of the trace structure in the rewriting field, in
its appendix, where we tried to sketch a very SHORT history of the
notion of feedback in theoretical computer science, with a particular
attention to the algebraic specification field. We found it interesting
to review previous approaches to the topic, after the results of
Joyal-Street-Verity have newly sparkled the interest in the algebraic
description of fixed points (see e.g. the recent paper by Selinger
advertised a few weeks ago on this mailing list).

Best regards,

Fabio Gadducci

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{abstract}
We present a categorical formulation of the rewriting of possibly cyclic
term graphs, based on a variation of algebraic 2-theories. We show that
this presentation is equivalent to the well-accepted operational
definition proposed by Barendregt et alii---but for the case of
``circular redexes'', for which we propose (and justify formally) a
different treatment. The categorical framework allows us to model in a
concise way
also automatic garbage collection and rules for sharing/unsharing and
folding/unfolding of structures, and to relate term graph rewriting to
other rewriting formalisms.
\end{abstract}

Paper announcement

[Peter Selinger]

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.

paper announcement

[Koslowski]

A heavily revised version of my paper "Beyond the Chu-construction"
is now available from my home page:

	http://www.iti.cs.tu-bs.de/~koslowj/RESEARCH/

It will eventually be published in Applied Categorical Structures.
I have not attempted to attribute the term "dualizing object" to anyone
in particular.  The open problem of an earlier version, as to whether
Cauchy-complete bicategories of interpolads inherit local *-autonomy 
from their base, has been answered affirmatively.  

Here is the abstract:


  Starting from symmetric monoidal closed (= autonomous) categories,
  Po-Hsiang Chu showed how to construct new *-autonomous categories,
  i.e., autonomous categories that are self-dual because of a
  dualizing object.  Recently, Michael Barr extended this to the
  non-symmetric, but closed, case, utilizing monads and modules
  between them.  Since these notions are well-understood for
  bicategories, we introduce a notion of local *-autonomy for these
  that implies closedness and, moreover, is inherited when forming
  bicategories of monads and of interpolads.  Since the initial step
  of Barr's construction also carries over to the bicategorical
  setting, we recover his main result as an easy corollary.
  Furthermore, the Chu-construction at this level may be viewed as a
  procedure for turning the endo-1-cells of a closed bicategory into
  the objects of a new closed bicategory, and hence conceptually is
  similar to constructing bicategories of monads and of interpolads.


Best regards,

-- J"urgen

-- 
J"urgen Koslowski       % If I don't see you no more in this world
ITI                     % I meet you in the next world
TU Braunschweig         % and don't be late!
koslowj@iti.cs.tu-bs.de %              Jimi Hendrix (Voodoo Child)

Paper Announcement

[Alex Simpson]

The following paper is available by anonymous FTP or over the Web

          Computational Adequacy in an Elementary Topos

  We place simple axioms on an elementary topos which suffice for it to 
  provide a denotational model of call-by-value PCF with sum and product
  types. The model is synthetic in the sense that types are interpreted
  by their set-theoretic counterparts within the topos. The main result
  characterises when the model is computationally adequate with respect
  to the operational semantics of the programming language. We prove that
  computational adequacy holds if and only if the topos is $1$-consistent
  (i.e. its internal logic validates only true $\Sigma^0_1$-sentences).

This paper is to appear in the forthcoming proceedings of CSL 98.

It is available from:

  http://www.dcs.ed.ac.uk/~als/Research/adequacy.ps.gz
  ftp://ftp.dcs.ed.ac.uk/pub/als/Research/adequacy.ps.gz

Best wishes,

Alex Simpson

-- 
Alex Simpson, LFCS, Division of Informatics, University of Edinburgh
Email: Alex.Simpson@dcs.ed.ac.uk             Tel: +44 (0)131 650 5113
FTP: ftp.dcs.ed.ac.uk/pub/als                Fax: +44 (0)131 667 7209  
URL: http://www.dcs.ed.ac.uk/home/als

Paper Announcement

[Alex Simpson]

The following paper is available by anonymous FTP or over the Web


    Lambda Definability with Sums via Grothendieck Logical Relations

                 by Marcelo Fiore and Alex Simpson

    We introduce a notion of *Grothendieck logical relation* and use 
    it to characterise the definability of morphisms in *stable* bicartesian
    closed categories by terms of the simply-typed lambda calculus with 
    finite products and finite sums. Our techniques are based on concepts 
    from topos theory, however our exposition is elementary.


The paper is written in a style appropriate for the conference

    Typed Lambda-Calculi and Applications

where it is to be presented in April. However, we briefly discuss
the true categorical content of the paper, which will be further 
expanded upon in a full version of the paper (forthcoming).

The paper is available over the Web:

    http://www.dcs.ed.ac.uk/~mf/TYPES/glr.{dvi,ps}
    http://www.dcs.ed.ac.uk/~als/Research/glr.ps.gz

or by anonymous FTP:

    ftp://ftp.dcs.ed.ac.uk/pub/mf/TYPES/glr.{dvi,ps}
    ftp://ftp.dcs.ed.ac.uk/pub/als/Research/glr.ps.gz

Best wishes for a happy New Year,

Alex Simpson

-- 
Alex Simpson, LFCS, Division of Informatics, University of Edinburgh
Email: Alex.Simpson@dcs.ed.ac.uk             Tel: +44 (0)131 650 5113
FTP: ftp.dcs.ed.ac.uk/pub/als                Fax: +44 (0)131 667 7209  
URL: http://www.dcs.ed.ac.uk/home/als