From MAILERDAEMON Mon Mar 31 09:43:14 2003
Date: 31 Mar 2003 09:43:14 0400
From: Mail System Internal Data
Subject: DON'T DELETE THIS MESSAGE  FOLDER INTERNAL DATA
MessageID: <1049118194@mta.ca>
XIMAP: 1046710820 0000000018
Status: RO
This text is part of the internal format of your mail folder, and is not
a real message. It is created automatically by the mail system software.
If deleted, important folder data will be lost, and it will be recreated
with the data reset to initial values.
From rrosebru@mta.ca Mon Mar 3 11:52:52 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 03 Mar 2003 11:52:52 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18ps9t0004vH00
for categorieslist@mta.ca; Mon, 03 Mar 2003 11:47:17 0400
MessageID: <3E6323AE.80107@tzi.de>
Date: Mon, 03 Mar 2003 10:43:10 +0100
From: Lutz Schroeder
UserAgent: Mozilla/5.0 (X11; U; Linux i686; enUS; rv:1.0.1) Gecko/20020903
XAcceptLanguage: enus, en
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: Inductive datatypes in toposes
References: <20030225195501.74658.qmail@web12001.mail.yahoo.com> <002001c2dd81$55acc1a0$b1e493d9@rmi.acnet.ge>
XEnigmailVersion: 0.63.3.0
XEnigmailSupports: pgpinline, pgpmime
ContentType: text/plain; charset=ISO88591; format=flowed
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 1
Dear categorists,
is there a good reference for the construction of inductive datatypes
(lists, trees etc.) in a topos with nno (assuming that my guess that
such a construction is indeed possible is correct)?
Thanks a lot,
Lutz Schr=F6der
=20
=

Lutz Schroeder Phone +494212184683
Dept. of Computer Science Fax +494212183054
University of Bremen lschrode@informatik.unibremen.de
P.O.Box 330440, D28334 Bremen
http://www.informatik.unibremen.de/~lschrode
=

From rrosebru@mta.ca Mon Mar 3 15:56:37 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 03 Mar 2003 15:56:37 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18pvzi0002XH00
for categorieslist@mta.ca; Mon, 03 Mar 2003 15:53:02 0400
Date: Mon, 3 Mar 2003 16:00:50 +0100 (CET)
From: "I. Moerdijk"
ReplyTo: "I. Moerdijk"
Subject: categories: master class in noncommutative geometry
To: categories@mta.ca
MIMEVersion: 1.0
ContentType: TEXT/plain; charset=usascii
XMailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
MessageId: <20030303150049.11419520C5@mail.math.uu.nl>
XVirusScanned: by AMaViS snapshot20020300
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 2
Dear colleagues,
during the next academic year, 20032004, we will organise a special
programme under the general heading of "noncommutative geometry" at
Utrecht. The lectures cover a range of topics, including homological
algebra, theory of C*algebras, foliations, and cyclic homology, and
are intended for students who would like to enter a PhD programme in
the subsequent year. There are some student grants available. If you
know of any students who might be interested, would you please direct
them to the following web page?
http://www.math.uu.nl/mri/education/master_0304.html
A brochure containing information on how to apply can be obtained from
there.
With best regards,
Ieke Moerdijk.
From rrosebru@mta.ca Mon Mar 3 15:56:37 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 03 Mar 2003 15:56:37 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18pw0W0002cF00
for categorieslist@mta.ca; Mon, 03 Mar 2003 15:53:52 0400
MessageID: <3E63818A.48AE09CB@labri.fr>
Date: Mon, 03 Mar 2003 17:23:38 +0100
From: Luigi Santocanale
Organization: LaBRI
XMailer: Mozilla 4.78 [fr] (X11; U; Linux 2.4.931 i686)
XAcceptLanguage: en
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: Re: Inductive datatypes in toposes
References: <20030225195501.74658.qmail@web12001.mail.yahoo.com> <002001c2dd81$55acc1a0$b1e493d9@rmi.acnet.ge> <3E6323AE.80107@tzi.de>
ContentType: text/plain; charset=iso88591
ContentTransferEncoding: quotedprintable
XVirusScanned: by amavisdnew
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 3
Lutz Schroeder a =E9crit :
>=20
> Dear categorists,
>=20
> is there a good reference for the construction of inductive datatypes
> (lists, trees etc.) in a topos with nno (assuming that my guess that
> such a construction is indeed possible is correct)?
Here are those I know:
=1F
@incollection {MR81f:18019,
AUTHOR =3D {Johnstone, Peter T. and Wraith, Gavin C.},
TITLE =3D {Algebraic theories in toposes},
BOOKTITLE =3D {Indexed categories and their applications},
SERIES =3D {Lecture Notes in Math.},
VOLUME =3D {661},
PAGES =3D {141242},
PUBLISHER =3D {Springer},
ADDRESS =3D {Berlin},
YEAR =3D {1978},
MRCLASS =3D {18B25 (18C10)},
MRNUMBER =3D {81f:18019},
}
@article {MR48:8597,
AUTHOR =3D {Lesaffre, Brigitte},
TITLE =3D {Structures alg\'ebriques dans les topos \'el\'ementaires}=
,
JOURNAL =3D {C. R. Acad. Sci. Paris S\'er. AB},
VOLUME =3D {277},
YEAR =3D {1973},
PAGES =3D {A663A666},
MRCLASS =3D {18C10 (02H10)},
MRNUMBER =3D {48 \#8597},
MRREVIEWER =3D {Andreas Blass},
}
For a subtopos structure:
@incollection {MR95h:68133,
AUTHOR =3D {Jay, C. Barry and Cockett, J. R. B.},
TITLE =3D {Shapely types and shape polymorphism},
BOOKTITLE =3D {Programming languages and systemsESOP '94 (Edinburgh,
1994)},
SERIES =3D {Lecture Notes in Comput. Sci.},
VOLUME =3D {788},
PAGES =3D {302316},
PUBLISHER =3D {Springer},
ADDRESS =3D {Berlin},
YEAR =3D {1994},
MRCLASS =3D {68Q65 (68N15)},
MRNUMBER =3D {95h:68133},
}
Best,
Luigi
=20
Luigi Santocanale
http://www.labri.fr/~santocan/
From rrosebru@mta.ca Mon Mar 3 15:57:03 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 03 Mar 2003 15:57:03 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18pw2K0002lH00
for categorieslist@mta.ca; Mon, 03 Mar 2003 15:55:44 0400
From: Thomas Streicher
MessageId: <200303031730.SAA17354@fb04209.mathematik.tudarmstadt.de>
Subject: categories: Re: Inductive datatypes in toposes
InReplyTo: <3E6323AE.80107@tzi.de> from Lutz Schroeder at "Mar 3, 2003 10:43:10
am"
To: categories@mta.ca
Date: Mon, 3 Mar 2003 18:30:18 +0100 (CET)
XMailer: ELM [version 2.4ME+ PL66 (25)]
MIMEVersion: 1.0
ContentType: text/plain; charset=USASCII
ContentTransferEncoding: 7bit
XMailScanner: Found to be clean
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 4
concerning the question
> is there a good reference for the construction of inductive datatypes
> (lists, trees etc.) in a topos with nno (assuming that my guess that
> such a construction is indeed possible is correct)?
The situation appears to me as follows.
I those toposes where IZF (intuitionistic Zermelo Fraenkel set theory) is
available (as e.g. Grothendieck and realizability toposes) business is as
usual for functors preserving \omegacolimits: you simply construct mu(F) as
colim_{n \in \omega} F^n(0). Notice, however, that there is a tacit appeal
to the axiom of replacement when constructing the family (F^n(0))_{n\in\omega}.
In general there is no reason why this family should exist. Of course, for the
above mentioned examples like lists, trees etc. you can construct such
inductive data types because both List(A) and Tree(A) appear as inductively
defined subsets of P(\tilde{A}^N) where \tilde{A} is the partial map
classifier. The reason is that trees and lists over A can be coded as partial
maps from N to A.
The point is that toposes (due to their impredicative nature) support inductive
definitions of predicates on a type A given in advance. However, they don't
support construction of inductively defined types as one cannot define
sufficiently many families of types.
It is not clear to me to which extent one can characterise those inductive
types that can be reduced to inductively defined predicates in HAH.
However, one knows that assuming Wtypes (`a la MartinLoef) one can reduce
most inductive types to Wtypes in extensional type theory. As far as I
understand that's the reason why Moerdijk and Palmgren introduced lccc's with
Wtypes as sort of ``predicative toposes''.
Thomas
From rrosebru@mta.ca Tue Mar 4 07:58:12 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 04 Mar 2003 07:58:12 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18qAx30001hQ00
for categorieslist@mta.ca; Tue, 04 Mar 2003 07:51:17 0400
From: Alex Simpson
XAuthenticationWarning: topper.inf.ed.ac.uk: apache set sender to als@localhost using f
To: categories@mta.ca
Subject: categories: Re: Inductive datatypes in toposes
MessageID: <1046742576.3e640630a95fb@mail.inf.ed.ac.uk>
Date: Tue, 04 Mar 2003 01:49:36 +0000 (GMT)
References: <200303031730.SAA17354@fb04209.mathematik.tudarmstadt.de>
InReplyTo: <200303031730.SAA17354@fb04209.mathematik.tudarmstadt.de>
MIMEVersion: 1.0
ContentType: text/plain; charset=ISO88591
ContentTransferEncoding: 8bit
UserAgent: IMP/PHP IMAP webmail program 2.2.8
XOriginatingIP: 130.54.16.90
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 5
Lutz Schroeder asked:
> > is there a good reference for the construction of inductive
> datatypes
> > (lists, trees etc.) in a topos with nno (assuming that my guess that
> > such a construction is indeed possible is correct)?
Thomas Streicher replied:
> It is not clear to me to which extent one can characterise those
> inductive
> types that can be reduced to inductively defined predicates in HAH.
> However, one knows that assuming Wtypes (`a la MartinLoef) one can
> reduce
> most inductive types to Wtypes in extensional type theory. As far as
> I
> understand that's the reason why Moerdijk and Palmgren introduced lccc's
> with
> Wtypes as sort of ``predicative toposes''.
Just to point out that "assuming Wtypes" here is no extra assumption.
Moerdijk and Palmgren observe that every elementary topos with nno
has Wtypes. This observation more than answers Schroeder's
original question affirmatively. See Moerdijk and Palmgren,
"Wellfounded trees in categories", APAL 104, 2000, for the
observation. I'm not sure whether they include the details (I
don't have the paper to hand), but it's not a hard exercise.
Alex Simpson
Alex Simpson, LFCS, Division of Informatics, Univ. of Edinburgh
Email: Alex.Simpson@ed.ac.uk Tel: +44 (0)131 650 5113
Web: http://www.dcs.ed.ac.uk/home/als Fax: +44 (0)131 667 7209
From rrosebru@mta.ca Tue Mar 4 18:36:54 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 04 Mar 2003 18:36:54 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18qKwF0005lt00
for categorieslist@mta.ca; Tue, 04 Mar 2003 18:31:07 0400
From: Thomas Streicher
MessageId: <200303041644.RAA25697@fb04305.mathematik.tudarmstadt.de>
Subject: categories: Wtypes in toposes
To: categories@mta.ca
Date: Tue, 4 Mar 2003 17:44:17 +0100 (CET)
XMailer: ELM [version 2.4ME+ PL66 (25)]
MIMEVersion: 1.0
ContentType: text/plain; charset=USASCII
ContentTransferEncoding: 7bit
XMailScanner: Found to be clean
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 6
Alex S. pointed out quite correctly that toposes with NNO allow one to
construct Wtypes Wx:A.B(x) for all b : B > A (where B(x) is a shorthand
for b^{1}(x)). The idea is as follows: elements of Wx:A.B(x) are thought of
as wellfounded terms over the signature A where B(a) is the arity of
operation with name a. Thus, possibly infinite terms over this signature can
be coded up as partial maps t : List(B) \parr A satisfying the conditions
(i) the domain of t is prefix closed
(ii) if t(s) is defined and equal a then t(s^y) is defined iff and only
if y \in B(a)
The term t is ``reachable'' iff dom(t) is an element of the least subset
T_B of P(List(B)) satisfying the closure conditions
 {<>} in T_B
 if a \in A and f : B(a) > T_B then
{<>} \cup { b^s  b \in B(a) & s \in f(b) }
Notice that ``reachable'' is more restrictive than wellfounded in a
constructive setting. Claiming that "wellfounded entails reachable" is
known as "bar induction".
Generally, Wtypes capture inductive types which are of the type "free term
algebra" albeit for very general signatures as given by a family of types.
It certainly contains all and more than what one thinks of in C.S. usually
when using the word inductive type.
However, necessarily "inductive type" is an "open" notion and heavily
syntaxdependent. There is the categorical generalization of inductive type
as initial fixpoint of a covariant functor F : EE>EE where EE is the ambient
topos or model of type theory. In a sense this a vacuous notion as you can get
every type A as initial fixpoint of F(X)=A. On the other hand, even in Set not
every covariant functor F : Set>Set needs to have a fixpoint (e.g. if F is
the covariant powerset functor). However, sometimes in categories different
from Set functor of the form F(X) = S^(S^X) do have fixpoints for particular
nontrivial S (for Sierpinski space).
The reason why I mentioned axiom of replacement is that in the business of
solving recursive domain equations the axiom of relacement is needed (see
Alex Simpson's paper from LICS02). But in any case for constructing free term
algebras we don't need it.
Nevertheless, there is still a nagging question about the relationship between
inductive predicates and inductive types. Can one characterise those
syntactically given covaraint functors F (constructed, say, from parameters
using sum, cartesian product and exponentiation) for which HAH proves the
existence of a fixpoint, in other words which inductive types are ensured by
higher order arithmetic?
Thomas S.
From rrosebru@mta.ca Thu Mar 6 15:10:11 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 06 Mar 2003 15:10:11 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18r0ed00001v00
for categorieslist@mta.ca; Thu, 06 Mar 2003 15:03:43 0400
To: categories@mta.ca
Subject: categories: BCTCS 19
XMailer: mhe 6.1; nmh 1.0.4+dev; Emacs 21.2
Date: Thu, 06 Mar 2003 14:41:34 +0000
From: N Ghani
MessageId:
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 7
**** ****
Please can you publicise this amongst your colleagues and particularly
PhD students who could take advantage of our grants for accommodation
etc
++
CALL FOR PARTICIPATION
British Colloquium on Theoretical Computer Science
7th  9th April 2003
Leicester, United Kingdom
http://www.mcs.le.ac.uk/events/bctcs19/
The British Colloquium for Theoretical Computer Science (BCTCS) is an
annual conference providing a forum for research in all areas of
theoretical computer science. As such, it aims to provide an informal
setting within which researchers can meet and discuss
recent developments and results in the broad swathe of the subject
rather than in just their own area of specialty.
The BCTCS is also dedicated to the development and training of
postgraduate research students. Indeed, the relaxed nature of the
conference provides an excellent environment where postgraduate
students may gain the experience of presenting their work to their
colleagues and benefit from contact with established researchers in
the community. A number of grants are available to fund the
accommodation and registration costs of postgraduate students who are
willing to give talks.
This year, we are pleased to have invited talks in the areas of
programming language semantics, category theory, algorithms, formal
languages and automata theory given by
Prof A. Jung, University of Birmingham, UK
Prof F.W. Lawvere, State University of New York, USA
Prof K. Mehlhorn, Universitaet des Saarlandes, Germany
Dr S. Muthukrishnan, Rutgers University, USA and AT&T
Prof. J. Pin, Universite Paris Denis Diderot et CNRS, France
Further details of the program etc will be available from the website
http://www.mcs.le.ac.uk/events/bctcs19/
and registration, travel, costs etc can be found at
http://www.le.ac.uk/conference/bctcs/
For any other issues, please contact bctcs19@mcs.le.ac.uk
Neil Ghani
Dr Conference Organiser
++
 Dr Neil Ghani Email : ng13@mcs.le.ac.uk 
 Dept of Maths and Computer Science Web : www.mcs.le.ac.uk/~ng13 
 University of Leicester 
 University Rd, 
 Leicester LE1 7RH Phone : +44 (0)116 252 3807 
 United Kingdom Fax : +44 (0)116 252 3915 
++
From rrosebru@mta.ca Mon Mar 10 11:45:24 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 10 Mar 2003 11:45:24 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18sPJg0001Ix00
for categorieslist@mta.ca; Mon, 10 Mar 2003 11:35:52 0400
To: categories@mta.ca
Subject: categories: Sets for Mathematics, new book available
Date: Sun, 09 Mar 2003 21:00:01 0500
From: wlawvere@buffalo.edu
MessageID: <1047261601.3e6bf1a1a5d1c@mail2.buffalo.edu>
XMailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.10 24Janua=
Status: RO
XStatus:
XKeywords:
XUID: 8
The book
SETS FOR MATHEMATICS
by F.W. Lawvere and R.Rosebrugh
which is listed in the Cambridge University Press catalogue, is finally
actually available. The main text is based on courses given several
times at Buffalo and Sackville for thirdyear students of mathematics,
computer science, and other mathematical sciences. Although more
advanced than the book Conceptual Mathematics by Lawvere and Schanuel
(which is aimed at total beginners) this text develops from scratch the
theory of the category of abstract sets and certain other toposes with
examples from elementary algebra, differential equations, and automata
theory.
Among the reasons offered in the appendix for developing an explicit
foundation is the need to have a basis for studying such works as
EilenbergSteenrod on algebraic topology and Grothendieck on functional
analysis and algebraic geometry. Indeed, the appendix lays down a
challenging definition of "foundation" which the book itself can only
begin to fulfill.
The basic concepts are treated with detailed explanations and with
many examples, both in the text and in exercises. After the basics are
available, some old topics can be treated in a unifying contemporary
spirit, for example
(1) The standard tools for analyzing an arbitrary map are the induced
equivalence relation, coequivalence relation, graph and cograph
(cographs have been very frequently pictured in practice but only rarely
recognized explicitly); all four of these are shown to arise inevitably
as Kan quantifications, along the two possible interpretations of the
generic map as half of the splitting of a generic idempotent.
(2) The socalled "measurable" cardinals can be excluded from a
topos by the intuitive demand that space and quantity have a good
duality, made explicit =E0 la Isbell via the requirement that there is a
fixed automaton such that the monad obtained by doubledualizing into it
is the identity.
The authors hope that this work will serve as one of the springboards
to the development and teaching of a foundation suitable for
twentyfirst century mathematics. Meanwhile the suggestions, criticisms
and corrections that colleagues may offer are eagerly awaited.
Corrections will be posted on the book home page at
http://www.mta.ca/~rrosebru/setsformath
From rrosebru@mta.ca Tue Mar 11 14:16:17 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 11 Mar 2003 14:16:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18soBR00028Q00
for categorieslist@mta.ca; Tue, 11 Mar 2003 14:09:01 0400
Date: Mon, 10 Mar 2003 15:02:55 GMT
From: Jeremy Gibbons
To: categories@mta.ca
Subject: categories: jobs: Postdoc & PhD positions in DatatypeGeneric programming
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 9
[We apologize if you receive multiple copies of this announcement.]
Postdoctoral research fellow (University of Nottingham)
Doctoral studentship (University of Oxford)
in DATATYPEGENERIC PROGRAMMING
The Universities of Nottingham and Oxford have positions available to work
on an EPSRCsupported project entitled "DatatypeGeneric Programming",
running for three years and starting on or shortly after 1st August
2003. There is a postdoctoral research fellowship at Nottingham, and a
DPhil studentship at Oxford.
The project is to develop a novel mechanism for parametrizing programs,
namely parametrization by a datatype or type constructor. The mechanism is
related to parametric polymorphism, but of higher order. We aim to develop
a calculus for constructing datatypegeneric programs, with the ultimate
goal of improving the state of the art in generic objectoriented
programming, as occurs for example in the C++ Standard Template Library.
Further details of the project can be obtained from the contacts listed
below.
Applicants for the postdoctoral fellowship should have completed (or
be about to complete) a PhD degree. Preference will be given to
applicants with an excellent knowledge of the calculational style of
reasoning. Expertise in functional programming, objectoriented
programming and the mathematics of program construction is
required. Send a detailed curriculum vitae and the names and addresses
of two referees to Professor Roland Backhouse, School of Computer
Science and Information Technology, University of Nottingham, Jubilee
Campus, Wollaton Road, Nottingham NG8 1BB, UK, rcb@cs.nott.ac.uk,
www.cs.nott.ac.uk/~rcb, from whom further details can also be
obtained. Electronic applications should be sent in PDF format; other
formats will not be accepted.
The ideal applicant for the DPhil studentship would have (or be about to
obtain) a first or uppersecond class honours degree or equivalent in
computer science, with expertise in functional programming, objectoriented
programming and the mathematics of program construction. The studentship
pays for all university and college fees, in addition to the standard EPSRC
maintenance grant. Applicants should follow the procedure described at
www.comlab.ox.ac.uk/oucl/courses/grad0203/dphil/requirements.html, but
should also mention this position in the application. For further details
contact Dr Jeremy Gibbons, Oxford University Computing Laboratory, Wolfson
Building, Parks Road, Oxford OX1 3QD, UK, jeremy.gibbons@comlab.ox.ac.uk,
www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html.
The closing date for applications for both positions is Monday 14th April
2003.
Roland Backhouse
Jeremy Gibbons

Jeremy.Gibbons@comlab.ox.ac.uk
Oxford University Computing Laboratory, TEL: +44 1865 283508
Wolfson Building, Parks Road, FAX: +44 1865 273839
Oxford OX1 3QD, UK.
URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html
From rrosebru@mta.ca Mon Mar 17 11:18:29 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 17 Mar 2003 11:18:29 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18uwHp0006QA00
for categorieslist@mta.ca; Mon, 17 Mar 2003 11:12:25 0400
MessageID: <3E75DFCF.30607@cs.mcgill.ca>
Date: Mon, 17 Mar 2003 09:46:39 0500
From: Prakash PANANGADEN
Organization: McGill University Computer Science Dept.
UserAgent: Mozilla/5.0 (X11; U; FreeBSD i386; enUS; rv:1.0.0) Gecko/20020911
XAcceptLanguage: enus, en
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: MFPS Call for participation
ContentType: text/plain; charset=ISO88591; format=flowed
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 10
You are invited to participate in the 19th Mathematical Foundations of=20
Programming Semantics held at the Centre de Recherche of Universit=E9 de=20
Montreal from Wednesday March 19th 2:00 pm to Saturday 22nd March 6pm.=20
The registration fees
are $100 (CAN $160) for regular participants and $50 (CAN $ 80) for=20
students.
Details of the programme, registration information and other details may=20
be found at
http://www.crm.umontreal.ca/MFPS03
The general announcement for MFPS may be found at:
http://www.math.tulane.edu/~mfps/mfps19.htm
=20
Prakash Panangaden =
=20
School of Computer Science
McGill University
prakash@cs.mcgill.ca =
=20
From rrosebru@mta.ca Thu Mar 20 09:56:17 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 20 Mar 2003 09:56:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18w0Pu0004gc00
for categorieslist@mta.ca; Thu, 20 Mar 2003 09:49:10 0400
MessageID:
From: icalp2003@TUE.nl
To: categories@mta.ca
Subject: categories: list accepted papers for ICALP 2003
Date: Wed, 19 Mar 2003 14:36:56 +0100
XMessageFlag: Follow up
MIMEVersion: 1.0
XMailer: Internet Mail Service (5.5.2656.59)
ContentType: text/plain;
Status: RO
XStatus:
XKeywords:
XUID: 11
=09charset=3D"iso88591"
Sender: catdist@mta.ca
Precedence: bulk

We apologize for the reception of multiple copies of this message.
=


=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
List of papers accepted for ICALP'2003, Track A and Track B
Eindhoven, The Netherlands, June 30  July 4, 2003
http://www.win.tue.nl/icalp2003/
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
Vincent Blondel, Paul Van Dooren
Similarity matrices for pairs of graphs
Arnold Schoenhage
Adaptive raising strategies optimizing relative efficiency
Sergei Bespamyatnikh, Michael Segal
Dynamic algorithms for approximating interdistances
Amos Korman, David Peleg
Labeling schemes for dynamic tree networks
Geraud Senizergues
The equivalence problem for tturn DPDA is coNP
John Hitchcock, Jack Lutz, Elvira Mayordomo
Scaled dimension and nonuniform complexity
Yossi Matias, Ely Porat
Efficient pebbling for list traversal synopses
Alexander Ageev, Yinyu Ye, Jiawei Zhang
Improved combinatorial approximation algorithms for the klevel facility
location problem
Markus Blaeser
An improved approximation algorithm for the asymmetric TSP with strengthene=
d
triangle inequality
Susanne Albers, Rob van Stee
A study of integrated document and connection caching
Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat
Function matching: algorithms, applications, and a lower bound
Eyal EvenDar, Alex Kesselman, Yishay Mansour
Convergence time to Nash equilibria
Amin CojaOghlan, Cristopher Moore, Vishal Sanwalani
MAX kCUT and approximating the chromatic number of random graphs
Jiri Fiala, Daniel Paulusma
The computational complexity of the role assignment problem
Vipul Bansal, Aseem Agrawal, Varun Malhotra
Stable marriages with multiple partners: efficient search for an optimal
solution
Juraj Hromkovic, Georg Schnitger
Pushdown automata and multicounter machines, a comparison of computation
mode
Jens Jaegerskuepper
Analysis of a simple evolutionary algorithm for minimization in Euclidean
spaces
Noam Berger, Bela Bollobas, Christian Borgs, Jennifer Chayes, Oliver Riorda=
n
Degree distribution of the FKP network model
Luisa Gargano, Mikael Hammar
There are spanning spiders in dense graphs (and we know how to find them)
Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro
Generalized framework for selectors with applications in optimal group
testing
Michael Elkin, Guy Kortsarz
Approximation algorithm for the directed telephone multicast problem
Sanjeev Arora, Kevin Chang
Approximation schemes for degreerestricted MST and redblue separation
problem
Surender Baswana, Sandeep Sen
A simple linear time algorithm for computing a (2k1)Spanner of
O(n^{1+1/k}) size in weighted graphs
Chandra Chekuri, Marcelo Mydlarz, Bruce Shepherd
Multicommodity demand flow in a tree
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor
Algorithmic aspects of bandwidth trading
Chandra Chekuri, Sudipto Guha, Joseph Naor
Approximating Steiner kcuts
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhis=
a
Makino
An intersection inequality for discrete distributions and related generatio=
n
problems
Erik Demaine, Fedor Fomin, MohammadTaghi Hajiaghayi, Dimitrios Thilikos
Fixedparameter algorithms for the (k,r)center in planar graphs and map
graphs
Gianni Franceschini, Roberto Grossi
Optimal cacheoblivious implicit dictionaries
Anna Gal, Peter Bro Miltersen
The cell probe complexity of succinct data structures,
Alex Hall, Steffen Hippler, Martin Skutella
Multicommodity flows over time: efficient algorithms and complexity
Rene Sitters, Leen Stougie, Willem Paepe
A competitive algorithm for the general 2server problem
Luis Antunes, Lance Fortnow
Sophistication revisited
Peter Hoyer, Michele Mosca, Ronald de Wolf
Quantum search on boundederror inputs
Dimitris Fotakis
On the competitive ratio for online facility location
Satoshi Ikeda, Izumi Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita
Impact of local topological information on random walks on finite graphs
Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger
Online load balancing made simple: greedy strikes back
Seffi Naor, Hadas Shachnai, Tami Tamir
Realtime scheduling with a budget
Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
Solving the robots gathering problem
Rainer Feldmann, Martin Gairing, Thomas Luecking, Burkhard Monien, Manuel
Rode
Nashification and the coordination ratio for a selfish routing game
Brian Dean, Michel Goemans
Improved approximation algorithms for minimumspace advertisement schedulin=
g
Baruch Awerbuch, Andre Brinkmann, Christian Scheideler
Anycasting in adversarial systems: routing and admission control
Jianer Chen, Iyad Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia
Genus characterizes the complexity of graph problems: some tight results
Markus Holzer, Martin Kutrib
Flippushdown automata: k+1 pushdown reversals are better than k
Manuel Bodirsky, Clemens Gr=F6pl, Mihyun Kang
Generating labeled planar graphs uniformly at random
Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasa=
n
An improved approximation algorithm for vertex cover with hard capacities
Dominique Poulalhon, Gilles Schaeffer
Optimal coding and sampling of triangulations
Ian Munro, Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti
Succinct representations of permutations
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
A direct sum theorem in communication complexity via message compression
Rajeev Raman, Srinivasa Rao
Succinct dynamic dictionaries and trees
Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung
Decoding of interleaved Reed Solomon codes over noisy data,
Juha K=E4rkk=E4inen, Peter Sanders
Simple linear work suffix array construction
Manfred Droste, Dietrich Kuske
Skew and infinitary formal power series
ErnstErich Doberkat
Semipullbacks and bisimulations in categories of stochastic relations
Stefan Blom, Wan Fokkink, Sumit Nain
On the axiomatizability of ready traces, ready simulation and failure trace=
s
Juraj Hromkovic, Georg Schnitger
Nondeterminisn versus determinism for twoway finite automata:
generalizations of Sipser's separation
Daniele Gorla, Rosario Pugliese
Resource access and mobility control with dynamic privileges acquisition
Jan Johannsen, Martin Lange
CTL+ is complete for double exponential time
Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca
Mixin modules and computational effects
Thierry Cachat
Higher order pushdown automata, the Caucal hierarchy of graphs and parity
games
Gaoyan Xie, Zhe Dang, Oscar Ibarra
A solvable class of quadratic Diophantine equations with applications to
verification of infinite state systems
Alexander Okhotin
Decision problems for language equations with Boolean operations
Roberto Bruni, Jose Meseguer
Generalized rewrite theories
Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato
Hierarchical and recursive state machines with contextdependent properties
Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van
Campenhout
The definition of a temporal clock operator
Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro
Replication vs. recursive definitions in channel based calculi
Richard Mayr
Undecidability of weak bisimulation equivalence for 1counter processes
Felix Klaedtke, Harald Ruess
Monadic secondorder logics with cardinalities
Orna Kupferman, Moshe Vardi
Pi_2 intersected Sigma_2 equals AFMC
Alexander Rabinovich
Quantitative analysis of probabilistic lossy channel systems
Massimo Merro, Francesco Zappa Nardelli
Bisimulation proof methods for mobile ambients
Tatiana Rybina, Andrei Voronkov
Upper bounds for a theory of queues
Zena Ariola, Hugo Herbelin
Minimal classical logic and control operators
Arnaud Carayol, Thomas Colcombet
On equivalent representations of infinite structures
Philippe Schnoebelen
Oracle circuits for branchingtime model checking
Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar
Discounting the future in systems theory
Thomas Henzinger, Ranjit Jhala, Rupak Majumdar
Counterexample guided control
Jo Hannay
Axiomatic criteria for quotients and subobjects for higherorder data types
Francois Denis, Yann Esposito
Residual languages and probabilistic automata
Francisco Gutierrez, Blas Ruiz
Expansion postponement via cut elimination in sequent calculi for pure type
systems
Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone
Secrecy in untrusted networks
Luca de Alfaro, Marco Faella
Information flow in concurrent games
Marielle Stoelinga , Frits Vaandrager
A testing scenario for probabilistic automata
Arkadev Chattopadhyay, Denis Therien
Locally commutative categories
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
From rrosebru@mta.ca Fri Mar 21 11:33:36 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 21 Mar 2003 11:33:36 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18wOOg0004lz00
for categorieslist@mta.ca; Fri, 21 Mar 2003 11:25:30 0400
Date: Wed, 19 Mar 2003 20:26:56 0800 (PST)
From: Galchin Vasili
Subject: categories: Alexandrov topology and Scott topology
To: categories@mta.ca
MIMEVersion: 1.0
ContentType: text/plain; charset=usascii
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 12
Hello,
A common example of a Heyting Algebra is one defined on an arbitrary
topology. In the cases of an Alexandrov topology and a Scott topology, are
either of these Boolean Algebras (special case of a HA) or purely Heyting
Algebras?
Regards, Bill Halchin
From rrosebru@mta.ca Sat Mar 22 16:28:39 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sat, 22 Mar 2003 16:28:39 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18wpUl0002f700
for categorieslist@mta.ca; Sat, 22 Mar 2003 16:21:35 0400
From: "C.F.Townsend"
To: "'categories@mta.ca'"
Subject: categories: Prime Ideal Theorem implies Excluded Middle?
Date: Sat, 22 Mar 2003 14:39:08 0000
MIMEVersion: 1.0
XMailer: Internet Mail Service (5.5.2448.0)
ContentType: text/plain; charset="iso88591"
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 13
Dear all, does anyone know a reference for the question:
Prime Ideal Theorem implies the Excluded Middle ?
Certainly, Axiom of Choice implies Excluded Middle, but I have convinced
myself that the weaker statement is true and would be grateful for any
pointers.
Regards, Christopher Townsend
PS there are definitely formulations of the PIT that do not use negation.
E.g. it is equivalent to the statement that for every Boolean alg. B if x in
B has the property that f(x)=0 for every Boolean alg. homomorphism
f:B>Omega, then x=0.
From rrosebru@mta.ca Sat Mar 22 17:35:11 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sat, 22 Mar 2003 17:35:11 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18wqcR0007Pc00
for categorieslist@mta.ca; Sat, 22 Mar 2003 17:33:35 0400
From: "Prof. Peter Johnstone"
To: categories
Subject: categories: Re: Prime Ideal Theorem implies Excluded Middle?
InReplyTo:
MessageID:
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
XScanner: exiscan for exim4 (http://duncanthrax.net/exiscan/) *18wqVj0002Q700*b.ZHBlOdy.g*
Sender: catdist@mta.ca
Precedence: bulk
Date: Sat, 22 Mar 2003 17:33:35 0400
Status: RO
XStatus:
XKeywords:
XUID: 14
On Sat, 22 Mar 2003, C.F.Townsend wrote:
> Dear all, does anyone know a reference for the question:
>
> Prime Ideal Theorem implies the Excluded Middle ?
>
My paper "Another condition equivalent to De Morgan's Law"
(Commun Alg. 7 (1979), 13091312) shows that the statement
"Every maximal ideal is prime" for distributive lattices
(or for Boolean algebras) is equivalent to De Morgan's law.
In a localic Settopos (assuming AC in Set) the Maximal
Ideal Theorem holds; hence in the topos of sheaves on an
extremally disconnected locale the Prime Ideal Theorem holds
(cf. Elephant, D4.6.15). But such a topos needn't be Boolean.
Peter Johnstone
From rrosebru@mta.ca Mon Mar 24 12:10:31 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 24 Mar 2003 12:10:31 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18xUPf0002ID00
for categorieslist@mta.ca; Mon, 24 Mar 2003 12:03:03 0400
Date: Mon, 24 Mar 2003 11:38:13 +0100 (CET)
From: Benno van den Berg
ReplyTo: Benno van den Berg
Subject: categories: Peripatetic Seminar on Sheaves and Logic
To: categories@mta.ca
MIMEVersion: 1.0
ContentType: TEXT/plain; charset=usascii
ContentMD5: BewHqF+XLZZOrmtZR8iX5g==
XMailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
MessageId: <20030324103812.C1803520C5@mail.math.uu.nl>
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 15
Dear all,
A PSSL will be organized by the University of Utrecht (in the Netherlands)
in the weekend of the 28th and 29th of June. I will launch a webpage where
the necessary information can be found. You will be informed as soon as it
is finished.
With best regards,
Benno

Benno van den Berg  Mathematisch Instituut, UU
vdberg@math.uu.nl  P.O.box 80.010, 3508 TA Utrecht, NL
From rrosebru@mta.ca Wed Mar 26 10:50:43 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 26 Mar 2003 10:50:43 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18yCA10001fa00
for categorieslist@mta.ca; Wed, 26 Mar 2003 10:45:49 0400
MessageID: <3E808ED6.6A831058@cmi.univmrs.fr>
Date: Tue, 25 Mar 2003 18:16:06 +0100
From:
Organization: Laboratoire d'Informatique Fondamentale de Marseille
XMailer: Mozilla 4.78 [fr] (X11; U; Linux 2.4.834.1mdk i686)
XAcceptLanguage: en
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: CONCUR 2003  Call for papers  Marseille, France
ContentType: text/plain; charset=iso88591
XMailScanner: Found to be clean
ContentTransferEncoding: quotedprintable
XMIMEAutoconverted: from 8bit to quotedprintable by gyptis.univmrs.fr id h2PHXB013862
Sender: catdist@mta.ca
Precedence: bulk
Status: RO
XStatus:
XKeywords:
XUID: 16
We apologize if you receive multiple copies of this message.
**********************************************************
**********************************************************
*** ***
*** CONCUR 2003 ***
*** ***
*** September, 35, 2003 ***
*** Marseille, France ***
*** ***
*** CALL FOR PAPERS ***
*** ***
**********************************************************
**********************************************************
CONCUR 2003, the 14th international conference on concurrency theory, is
organized by the Laboratoire d'Informatique Fondamentale de Marseille (LI=
F).
The purpose of the CONCUR conferences is to bring together researchers,
developers and students in order to advance the theory of concurrency, an=
d
promote its applications. Interest in this topic is continuously growing,=
as
a consequence of the importance and ubiquity of concurrent systems and th=
eir
applications, and of the scientific relevance of their foundations.=20
Submissions are solicited in all areas of semantics, logics and verificat=
ion
techniques for concurrent systems. Principal topics include (but are not
limited to):
 Basic models and logics of concurrent and distributed computation
(such as process algebras, Petri nets, domain theoretic or game
theoretic models, modal and temporal logics).=20
 Specialized or enriched models (such as circuits, synchronous
systems, real time and hybrid systems, stochastic systems, data
bases, mobile and migrating systems, parametric protocols,
security protocols).=20
 Related verification techniques and tools (such as statespace
exploration, modelchecking, synthesis, abstraction, automated
deduction, testing).=20
 Related programming models (such as distributed, constraints or
object oriented, graph rewriting, as well as associated type syste=
ms,
static analyses, abstract machines, and environments).=20
Authors are invited to submit an extended abstract not exceeding 15 pages
electronically via the web submission form at the conference's web site.
Submissions will be evaluated by the program committee for inclusion in t=
he
proceedings, which will be published by SpringerVerlag in the Lecture No=
tes in
Computer Science series. Papers must contain original contributions, be c=
learly
written, and include appropriate reference to and comparison with related=
work.
Simultaneous submissions to other conferences are not allowed.=20
Important dates=20
Submission: April 4, 2003 > There will be no deadline extension.
Notification: May 26, 2003=20
Final version: June 10, 2003=20
Workshops: September 2,6, and 7, 2003=20
Program committee=20
Roberto Amadio, chair (Marseille) Denis Lugiez, cochair (Marseil=
le)=20
David Basin (Zurich) Madhavan Mukund (Chennai)=20
Julian Bradfield (Edinburgh) Doron Peled (Austin)=20
Witold Charatonik (Wroclaw) JeanFran=E7ois Raskin (Brussel=
s)=20
Alessandro Cimatti (Trento) Roberto Segala (Verona)=20
Philippa Gardner (London) Eugene Stark (StonyBrook)=20
Patrice Godefroid (MurrayHill) Peter Van Roy (LouvainlaNeuve=
)=20
Holger Hermanns (Twente) Thomas Wilke (Kiel)=20
Naoki Kobayashi (Tokyo) Glynn Winskel (Cambridge)=20
Kim Larsen (Aalborg)=20
Invited speakers=20
Albert Benveniste (Rennes) Nancy Lynch (Boston)=20
Luca De Alfaro (SantaCruz) Andre Scedrov (Philadelphia)=20
More informations available at the conference's web site
http://concur03.univmrs.fr
From rrosebru@mta.ca Sun Mar 30 15:36:57 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 30 Mar 2003 15:36:57 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18ziUa0002fl00
for categorieslist@mta.ca; Sun, 30 Mar 2003 15:29:20 0400
Date: Fri, 28 Mar 2003 15:48:27 0500 (EST)
From: Peter Freyd
MessageId: <200303282048.h2SKmRVN022142@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: categorist makes good?
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 17
Copyright 2003 Vietnam News Briefs
Vietnam News Briefs
March 28, 2003
LENGTH: 95 words
HEADLINE: SOCIAL & CULTURAL ISSUES: FEMALE VIETNAMESE SCIENTISTS
RECEIVE FRENCH ORDER
BODY: The French Government has awarded the French Order of Academic
Palms to two Vietnamese scientists, Le Hong Sam and Hoang Xuan Sinh,
for their contributions to boosting cooperation in culture and science
between the two nations. Ms Sam is a researcher on French literature
and currently works for the National University of Social Sciences &
Humanities in Hanoi. Ms Sinh, a mathematician, is the principal of the
Thang Long Open University in Hanoi.
The presentation ceremony was held at the French Embassy in Hanoi on
March 25.
**********************************************************************
Her papers, as adapted from MathSciNet:
Hoang Xuan Sinh
Grcategories strictes. (French)
Acta Math. Vietnam. 3 (1978), no. 2, 4759.
18D10 (20J05 20L10)
A Grcategory is a groupoid P which is a monoidal category with
product and unit such that each object X of P has an inverse
(X', t, p), where t:X'*X > 1 and p:X*X' > 1. It is called a
strict Grcategory if it is a strict monoidal category and t and p
are identities for every X. The main theorem of this paper states
that every Grcategory is Grequivalent to a strict Grcategory...The
proof of this theorem uses a result of the author's thesis at the
University of Paris VII, 1975 which is that every Grcategory P is
determined up to a Grequivalence by two groups...As an application of
the results of this paper, the author proves Lemma 9.1 of S. Eilenberg
and S. Mac Lane [Ann. of Math. (2) 48 (1947), 326341; MR 9, 7] on
the realization of a 3cocycle as the obstruction of a problem of
extension.
Reviewed by J. L. Williams
Hoang Xuan Sinh
Categories de Picard restreintes. (French)
[Restricted Picard categories]
Acta Math. Vietnam. 7 (1982), no. 1, 117122 (1983).
18E99
>From the text: "A Picard category is a Grcategory equipped with a
commutativity constraint compatible with its associativity constraint.
A Picard category P is said to be restricted if its commutativity
constraint c satisfies c_{x,x}= identity for all objects x. We
represent every Picard category by a complex of chains and we deduce
that the classification of restricted prefastened (`preepinglees')
Picard categories of type (M,N) is trivial."
From rrosebru@mta.ca Sun Mar 30 15:36:57 2003 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 30 Mar 2003 15:36:57 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18ziY50002rD00
for categorieslist@mta.ca; Sun, 30 Mar 2003 15:32:57 0400
Date: Sat, 29 Mar 2003 17:34:26 0500 (EST)
From: F W Lawvere
XSender: wlawvere@hercules.acsu.buffalo.edu
ReplyTo: wlawvere@acsu.buffalo.edu
To: categories@mta.ca
Subject: categories: Grothendieck's 1973 Buffalo Colloquium
MessageID:
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
Status: RO
XStatus:
XKeywords:
XUID: 18
Thierry Coquand recently asked me
> In your "Comments on the Development of Topos Theory" you refer
> to a simpler alternative definition of "scheme" due to Grothendieck.
> Is this definition available at some place?? Otherwise, it it possible
> to describe shortly the main idea of this alternative definition??
Since several people have asked the same question over the years, I
prepared the following summary which, I hope, will be of general interest:
The 1973 Buffalo Colloquium talk by Alexander Grothendieck had as
its main theme that the 1960 definition of scheme (which had required as a
prerequisite the baggage of prime ideals and the spectral space, sheaves
of local rings, coverings and patchings, etc.), should be abandoned AS the
FUNDAMENTAL one and replaced by the simple idea of a good functor from
rings to sets. The needed restrictions could be more intuitively and more
geometrically stated directly in terms of the topos of such functors, and
of course the ingredients from the "baggage" could be extracted when
needed as auxiliary explanations of already existing objects, rather than
being carried always as core elements of the very definition.
Thus his definition is essentially wellknown, and indeed is
mentioned in such texts as DemazureGabriel, Waterhouse, and Eisenbud;
but it is not carried through to the end, resulting in more
complication, rather than less. I myself had learned the functorial point
of view from Gabriel in 1966 at the StrasbourgHeidelbergOberwolfach
seminar and therefore I was particularly gratified when I heard
Grothendieck so emphatically urging that it should replace the one
previously expounded by Dieudonne' and himself.
He repeated several times that points are not mere points, but
carry Galois group actions. I regard this as a part of the content of his
opinion (expressed to me in 1989) that the notion of
topos was among his most important contributions. A more general
expression of that content, I believe, is that a generalized "gros" topos
can be a better approximation to geometric intuition than a category
of topological spaces, so that the latter should be relegated to an
auxiliary position rather than being routinely considered as "the" default
notion of cohesive space. (This is independent of the use of localic
toposes, a special kind of petit which represents only a minor
modification of the traditional view and not even any modification in the
algebraic geometry context due to coherence). It is perhaps a reluctance
to accept this overthrow that explains the situation 30 years later, when
Grothendieck's simplification is still not widely considered to be
elementary and "basic".
To recall some wellknown ingredients, let A be the category of
finitelypresented commutative algebras over k (or a larger category
closed under the symmetric algebra functor, for some purposes). Then the
underlying set functor R on A serves as the "line", and any system of
polynomial equations with coefficients in k determines also a functor (sub
space of Rn) in the wellknown way; in fact, the idea of spec is simply
identified with the Yoneda embedding of A^op. For example, R has a
subfunctor U of invertible elements and another U' such that
U'(A) = {ff in A, 1/1f in A}. The Grothendieck topology for which U and
U' together cover R yields a subtopos Z known as the gros Zariski topos,
which turns out to be the classifying topos for local kalgebras in any
topos. This Z contains all algebraic schemes over k, but also function
spaces Y^X and distribution spaces Hom(R^X,R) for all X,Y in Z. A basic
open subspace of any space X is determined as the pullback U sub f of U
under any map f: X>R. One has obviously U sub f intersection U sub g =
U sub fg and the intrinsic notion of epimorphism in Z gives a notion of
covering. Thus for a space (functor) to have a finite open covering, each
piece of which is representable, is a restrictive notion available when
needed.
A point of X is a map spec(L) > X where L is a field extension
of k.Thus the "points functor" on spaces goes not to the category of
abstract sets but rather is just the restriction operation to the category
of functors on fields only. This is part of what Grothendieck seems to
have had in mind. A serious discontinuity is introduced by passing to the
single underlying set traditionally considered, which is the inductive
limit of the functor of fields. The fact that the latter process does not
preserve products, and hence for example that an algebraic group "is not a
group", was already for Cartier an indication that the traditional
foundation had an unnatural ingredient, but before topos theory one tried
to live with it (for example, I recall great geometers from the 1950s
struggling to accept the new wisdom that +i and i is one "point"). The
acceptance of the view that, for nonalgebraicallyclosed k, the
appropriate base topos consists not of pure sets but rather of sheaves on
just the simple objects in A, has in fact many simplifying conceptual and
technical advantages; for example this base (in some sense due to
Galois!) is at least qd in the sense of Johnstone, and even atomic Boolean in
the sense of Barr.
(Technically, to verify that the above limitation to "algebraic" A
gives the usual results requires the use of a Birkhoff Nullstellensatz
which guarantees that there are "enough" algebras which are
finitelygenerated as kmodules. The use of a larger A, insuring for
example that spaces of distributions are often themselves representable,
is quite possible, but the precise description of the kind of double
structure which is then topostheoretically classified needs to be worked
out. Gaeta's notes of Grothendieck's lecture series at Buffalo point out
that A is more closely suited than most categories to serve as a site for
a geometric category, because it is what is now called "extensive" )
I believe that Grothendieck's point of view could be applied to
real algebraic geometry as well, in several ways, including the following:
Noting that within any topos the adjoint is available which assigns the
ring R[1] to any rig R, let us concentrate on the needed nature of
positive quantities R. To include the advantages of differential calculus
based on nilpotent elements, let us allow that the ideal of all elements
having negatives can be nontrivial, and indeed include many
infinitesimals, without disqualifying R from being "nonnegative". The ring
generated by R might appear in a more geometric way as the fiber of R^T,
where T is the representor for the tangentbundle functor. The
classifying topos for the theory of "real rigs", i.e., those for which
1/1+x is a given global operation, contains the classifying topos for
"really local rigs" in the following sense (where "really" has the double
meaning of (1) a strengthening of localness, but also (2) a concept
appropriate to a real (as opposed to complex) environment): The subspace U
of invertible elements in the generic algebra R has a classifying map
R > omega which of course as above preserves products; but the
distributive lattice omega is in particular also a rig like R, so we can
require that the classifying map be a rig homomorphism (i.e., also take +
to "union"). (Of course, this elementary condition can be phrased in terms
of subspaces of R and of R^2 without involving omega if desired.) The
preservation of addition is a strengthening, possible for positive
quantities, of the usual notion of localness (which on truth values was
only an inequality).
Does the right adjoint to ( )^T restrict to this really local rig
classifier?
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 142602900 USA
Tel. 7166456284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Mon Mar 31 09:43:29 2003 0400
Status:
XStatus:
XKeywords:
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 31 Mar 2003 09:43:29 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18zzXw0003vo00
for categorieslist@mta.ca; Mon, 31 Mar 2003 09:41:56 0400
Date: Sun, 30 Mar 2003 21:22:43 0500
From: Colin McLarty
Subject: categories: Re: Grothendieck's 1973 Buffalo Colloquium
Inreplyto:
XSender: cxm7@pop.cwru.edu (Unverified)
To: categories@mta.ca
Messageid: <5.2.0.9.0.20030330210746.00b33d90@pop.cwru.edu>
MIMEversion: 1.0
XMailer: QUALCOMM Windows Eudora Version 5.2.0.9
Contenttype: text/plain; charset=iso88591; format=flowed
Contenttransferencoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
I was just looking at Grothendieck's statement about schemes in EGA 3:
Pour obtenir un langage qui ``colle" sans effort =E0 l'intuition=20
g\'{e}om\'{e}trique, et \'{e}viter des circonlocutions
insupportables \`{a} la longue, nous identifions toujours un=20
pr\'{e}sch\'{e}ma $X$ sur un autre $S$ au foncteur
\mbox{\clarrow{(\mathrm{Sch}/S)^\mathrm{o}}{\mathrm{Ens}}} qu'il=20
repr\'{e}sente,
"To make the language stick to geometric intuition, and to avoid finally=20
unbearable circumlocutions, we will always identify a scheme X over another=
=20
S, with the functor from Sch/S to Set that it represents."
This quote is from the Springer Verlag edition page VI. This edition was=20
printed in 1970. I do not yet know if it is printed in the earlier IHES=20
edition.
The IHES edition of EGA chapter 0, printed in 1960, does urge the=20
functorial rather than topological space conception of a sheaf. "We=20
systematically abstain from using espaces etales ... we never consider a=20
sheaf a topological space" (p. 25).
best, Colin
___________________________________________________________
t 17:34 29/03/2003 0500, Lawvere wrote:
>Thierry Coquand recently asked me
>
> > In your "Comments on the Development of Topos Theory" you refer
> > to a simpler alternative definition of "scheme" due to Grothendieck.
> > Is this definition available at some place?? Otherwise, it it possible
> > to describe shortly the main idea of this alternative definition??
>
>Since several people have asked the same question over the years, I
>prepared the following summary which, I hope, will be of general interest:
>
> The 1973 Buffalo Colloquium talk by Alexander Grothendieck had as
>its main theme that the 1960 definition of scheme (which had required as a
>prerequisite the baggage of prime ideals and the spectral space, sheaves
>of local rings, coverings and patchings, etc.), should be abandoned AS the
>FUNDAMENTAL one and replaced by the simple idea of a good functor from
>rings to sets. The needed restrictions could be more intuitively and more
>geometrically stated directly in terms of the topos of such functors, and
>of course the ingredients from the "baggage" could be extracted when
>needed as auxiliary explanations of already existing objects, rather than
>being carried always as core elements of the very definition..
From rrosebru@mta.ca Mon Mar 31 09:46:08 2003 0400
Status:
XStatus:
XKeywords:
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 31 Mar 2003 09:46:08 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 18zzbq0004Pt00
for categorieslist@mta.ca; Mon, 31 Mar 2003 09:45:58 0400
Date: Sun, 30 Mar 2003 12:19:28 0500 (EST)
From: "NASSLLI'03 Bloomington, Indiana"
XSender: nasslli@lear.ucs.indiana.edu
ReplyTo: "NASSLLI'03 Bloomington, Indiana"
To: Undisclosed recipients: ;
Subject: categories: NASSLLI 2003. Registration is open now.
MessageID:
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
Registration for NASSLLI 2003 is now open.
For details, please visit
http://www.indiana.edu/~nasslli/registration.html

NASSLLI 2003
http://www.indiana.edu/~nasslli
The main focus of NASSLLI is on the interface between linguistics, logic,
and computation, broadly conceived, and on related fields. NASSLLI is a
weeklong summer school featuring courses on many topics of interest to
students and researchers. Some of the course topics are introductory,
while others are advanced courses that bring students to areas of active
research.
The instructors are leading researchers who like teaching in
interdisciplinary settings. Three of the courses involve work in computer
labs as well.
Please join us for a week of learning!

Registration
Registration does not include accommodations. We have arranged rooms in a
renovated, airconditioned dormitory at the rate of $37/night/person + 11%
tax. These are single rooms with a bathroom shared between two rooms. You
will need to pay for this when you are here with cash, check, MasterCard
or Visa. To reserve one of these rooms please send an email to
nasslli@indiana.edu , detailing for which days you will need the room.
In addition, our page on hotels lists some other housing options.
http://www.indiana.edu/~nasslli/hotels.html

Register for NASSLLI alone
Before May 1 After May 1
Fulltime Student $135 $150
Academic $200 $225
Industrial $280 $315

Register for MoL alone
To register for MoL alone, without NASSLLI: $43.

Register for TARK alone
To register for TARK alone, without NASSLLI: For students: $100
For others: $150

Register for NASSLLI + TARK
Before May 1 After May 1
Fulltime Student $210 $225
Academic $325 $350
Industrial $405 $440
From rrosebru@mta.ca Mon Mar 31 16:58:46 2003 0400
Status: R
XStatus:
XKeywords:
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 31 Mar 2003 16:58:46 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
id 1906FX0001ka00
for categorieslist@mta.ca; Mon, 31 Mar 2003 16:51:23 0400
MimeVersion: 1.0
XSender: duskin@mail.buffnet.net
MessageId:
Date: Mon, 31 Mar 2003 15:11:39 0500
To: categories@mta.ca
From: John Duskin
Subject: categories: Vietnamese Mathematician
ContentType: text/plain; charset="usascii" ; format="flowed"
Sender: catdist@mta.ca
Precedence: bulk

The mathematician from Hanoi recently honored by the French , Hoang
Xuan Sinh, was a student of Grothendieck. Her thesis was on
Grcategories.