From rrosebru@mta.ca Sat Mar 4 02:51:34 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id CAA22994
for categories-list; Sat, 4 Mar 2000 02:08:35 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Andrej.Bauer@CS.cmu.edu
To: categories@mta.ca
Subject: categories: Topos theory and large cardinals
Date: 01 Mar 2000 22:29:58 -0500
Message-ID:
Lines: 13
User-Agent: Gnus/5.0803 (Gnus v5.8.3) XEmacs/20.4 (Emerald)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Source-Info: Sender is really andrej+@gs2.sp.cs.cmu.edu
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Can you complete this analogy?
``Large cardinals are to ZFC, as ???? are to topos theory.''
One answer is "Grothendieck universes", but they correspond to rather
small large cardinals. Can we go further than that?
--
Andrej Bauer
School of Computer Science
Carnegie Mellon University
http://andrej.com
From rrosebru@mta.ca Sat Mar 4 03:06:49 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id CAA29524
for categories-list; Sat, 4 Mar 2000 02:24:53 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Fri, 3 Mar 2000 21:28:42 GMT
Message-Id: <200003032128.VAA02592@bruno.dcs.qmw.ac.uk>
From: Adam Eppendahl
To: categories@mta.ca
Subject: categories: dom fibration
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Can anyone explain why the codomain fibration cod: C^\rightarrow -> C,
which requires pull-backs, gets loads of attention, while the domain
fibration dom: C^rightarrow -> C, which works for all C, hardly gets a
look in? Is the dom fibration really such a poor relation?
Adam Eppendahl
From rrosebru@mta.ca Sat Mar 4 14:55:12 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id OAA06502
for categories-list; Sat, 4 Mar 2000 14:01:32 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
To: categories
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Date: Mon, 28 Feb 2000 12:35:46 +0000 (GMT)
From: Ronnie Brown
Subject: categories: review of `History of Topology'
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
I have put my review of `History of Topology', (ed I M James)
(North/Holland Elsevier) for the London Math Soc Newsletter linked from my
home page
http://www.bangor.ac.uk/~mas010#History
This review has some remarks on category theory, groupoids, etc.
Comments welcome!
Ronnie Brown
From rrosebru@mta.ca Sat Mar 4 15:59:19 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id PAA24694
for categories-list; Sat, 4 Mar 2000 15:08:05 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Fri, 3 Mar 2000 12:31:07 -0300 (EST)
From: Ruy de Queiroz
X-Sender: ruy@limoeiro
To: categories@mta.ca
Subject: categories: 7th WoLLIC'2000
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
[Please post. Apologies for multiple copies.]
Call for Contributions
7th Workshop on Logic, Language, Information and Computation
(WoLLIC'2000)
August 15-18, 2000
! TUTORIALS >> (Tutorial Day: August 15th) << TUTORIALS !
Natal, Brazil
The "7th Workshop on Logic, Language, Information and Computation"
(WoLLIC'2000), the seventh version of a series of workshops which started
in 1994 with the aim of fostering interdisciplinary research in pure and
applied logic, will be held in Natal, Brazil, from August 15th to 18th 2000.
Contributions are invited in the form of short papers (10 A4 10pt pages) in
all areas related to logic, language, information and computation, including:
pure logical systems, proof theory, model theory, algebraic logic, type theory,
category theory, constructive mathematics, lambda and combinatorial calculi,
program logic and program semantics, logics and models of concurrency,
logic and complexity theory, nonclassical logics, nonmonotonic logic,
logic and language, discourse representation, logic and artificial
intelligence, automated deduction, foundations of logic programming,
logic and computation, and logic engineering.
The 7th WoLLIC'2000 has the scientific sponsorship of the Association
for Symbolic Logic (ASL), the Interest Group in Pure and Applied Logics
(IGPL), the European Association for Logic, Language and Information (FoLLI),
the Sociedade Brasileira de Computacao (SBC), and the Sociedade Brasileira
de Logica (SBL).
THE LOCATION
Natal is the capital and largest city of Rio Grande do Norte, a sun shiny
land of beaches, dunes, coconut trees, located in north-east coast of Brazil.
There, the summer takes all year long (sun shines more than 300 days per
year), and the heat is softened by a constant breeze. Along the 400-kilometer
(250-mile) coast line, calm beaches with reefs forming natural pools altern
with good surfing spots, almost untouched places full of sand dunes and
coconut trees.
GUEST SPEAKERS
There will be a number of guest speakers, including:
Andrea Asperti (Univ Bologna, Italy)
Angus Macintyre (Edinburgh Univ, Scotland)
Luiz Carlos Pereira (Pontificial Catholic Univ of Rio, Brazil)
Toniann Pitassi (Arizona Univ, USA)
Bruno Poizat (Univ Lyon I, France)
Glynn Winskel (BRICS, Denmark)
SUBMISSION:
Papers (up to 10 pages A4 10pt, sent preferably in postscript format by
e-mail to wollic@di.ufpe.br, or in 5(five) copies to postal address) must
be RECEIVED by MAY 7th, 2000 by the Chair of the Organising Committee.
Papers must be ANONYMOUS (a separate identification page must be included),
written in English and give enough detail to allow the programme committee
to assess the merits of the work. Papers should start with a brief
statement of the issues, a summary of the main results, and a statement
of their significance and relevance to the workshop. References and
comparisons with related work is also expected. Technical development
directed to the specialist should follow. Results must be unpublished
and not submitted for publication elsewhere, including the proceedings
of other symposia or workshops. One author of each accepted paper will be
expected to attend the conference in order to present it. Authors will be
notified of acceptance by JUNE 9th, 2000, and final versions will have
to be delivered (in LaTeX format) by JUNE 16th, 2000. The abstracts of
the papers will be published in a "Conference Report" section of the
Logic Journal of the IGPL (ISSN 1367-0751) (Oxford Univ Press) as part
of the meeting report. Papers presented at the meeting will be invited for
submission (in full version) to the Logic Journal of the IGPL
(http://www.oup.co.uk/igpl/).
IMPORTANT DATES:
Submission: May 7th, 2000
Notification of acceptance/rejection: June 9th, 2000
Delivery of final (in LaTeX): June 16th, 2000
PROGRAMME COMMITTEE:
Sergei Artemov (Moscow Univ, Russia, and Cornell Univ, USA),
Ricardo Bianconi (Univ Sao Paulo, Brazil),
Sam Buss (UC San Diego, USA),
Edmund Clarke (Carnegie-Mellon Univ, USA),
Itala D'Ottaviano (Univ Campinas, Brazil),
Heinz-Dieter Ebbinghaus (Univ Freiburg, Germany),
Peter Johnstone (Cambridge Univ, UK),
Hans Kamp (Univ Stuttgart, Germany),
Pat Lincoln (SRI International, USA),
Maarten de Rijke (Amsterdam Univ, The Netherlands),
Colin Stirling (Edinburgh Univ, Scotland).
ORGANISING COMMITTEE:
B. C. Bedregal (UFRN),
M. E. Coniglio (UNICAMP),
A. M. P. Cruz (UFRN),
D. Deharbe (UFRN),
A. T. C. Martins (UFC),
A. Moreira (UFRN),
A. G. de Oliveira (UFPE/UFBA),
R. de Queiroz (UFPE),
R. H. N. Santiago (UFRN).
For further information, contact the Chair of the Organising Committee:
Ruy de Queiroz, Centro de Informatica, Univ. Federal de Pernambuco,
CP 7851, 50732-970 Recife, PE, Brazil. E-mail: ruy@di.ufpe.br,
tel.: (+55 81) 271-8430, fax: (+55 81) 271-8438.
WEB PAGE: http://www.di.ufpe.br/~wollic/wollic2000/
From rrosebru@mta.ca Mon Mar 6 09:36:11 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA06312
for categories-list; Mon, 6 Mar 2000 08:21:10 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Mon, 6 Mar 2000 12:14:14 +0000 (GMT)
From: Ronnie Brown
To: categories
Subject: categories: Re: review of `History of Topology'
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Apologies - I got my html ideas wrong. The url should be
http://www.bangor.ac.uk/~mas010/#History
or direct to
http://www.bangor.ac.uk/~mas010/lmsrev2.html
Ronnie Brown
On Mon, 28 Feb 2000, Ronnie Brown wrote:
>
>
> I have put my review of `History of Topology', (ed I M James)
> (North/Holland Elsevier) for the London Math Soc Newsletter linked from my
> home page
>
> http://www.bangor.ac.uk/~mas010#History
Prof R. Brown,
School of Informatics, Mathematics Division,
University of Wales, Bangor
Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom
Tel. direct:+44 1248 382474|office: 382475
fax: +44 1248 361429
World Wide Web:
home page: http://www.bangor.ac.uk/~mas010/
(Links to survey articles:
Higher dimensional group theory
Groupoids and crossed objects in algebraic topology)
Symbolic Sculpture and Mathematics:
http://www.bangor.ac.uk/SculMath/
Mathematics and Knots:
http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm
From rrosebru@mta.ca Mon Mar 6 09:36:18 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA07005
for categories-list; Mon, 6 Mar 2000 08:22:31 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Mime-Version: 1.0
X-Sender: street@hera.mpce.mq.edu.au
Message-Id:
In-Reply-To: <200003032128.VAA02592@bruno.dcs.qmw.ac.uk>
References: <200003032128.VAA02592@bruno.dcs.qmw.ac.uk>
Date: Mon, 6 Mar 2000 14:01:47 +1100
To: categories@mta.ca
From: Ross Street
Subject: categories: Re: dom fibration
Content-Type: text/plain; charset="us-ascii" ; format="flowed"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
>Can anyone explain why the codomain fibration cod: C^\rightarrow -> C,
>which requires pull-backs, gets loads of attention, while the domain
>fibration dom: C^rightarrow -> C, which works for all C, hardly gets a
>look in? Is the dom fibration really such a poor relation?
I have a couple of points to make about this.
1) By duality, the "poor relation" fibration dom can be
viewed as the opfibration cod. So it is not so poor after all, just
part of an even richer structure of cod.
2) Fibrations over C "amount" to pseudofunctors C^op -->
Cat. Let S be the pseudofunctor S(u) = C/u on objects, using
pullback on arrows; this is the "rich guy". The "poor guy" T is a
covariant functor (not just pseudo) T(u) = C/u , using composition
on arrows. To get a contravariant Cat-valued functor on C, follow
T by the presheaf construction P : Cat^coop --> Cat. It turns out
then that the Yoneda embedding gives a fully faithful pseudonatural
transformation y : S --> PT. Now PT is a very important
character; every internal full subcategory of the topos E of
presheaves on C is a full subobject of PT. (A good example is
where E is globular sets and PT is the globular category of
higher spans.) It is true that S can be thought of as an internal
model of E in Cat(E) leading to indexed (or parametrized)
category theory. But the reason this works well is that S is a full
subobject of PT. Again T wins out!
Regards,
Ross
From rrosebru@mta.ca Wed Mar 8 11:48:17 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id KAA19861
for categories-list; Wed, 8 Mar 2000 10:01:39 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Koslowski
Message-Id: <200003081343.OAA26111@lisa.iti.cs.tu-bs.de>
Subject: categories: PSSL 73, online registration
To: categories@mta.ca (categories list)
Date: Wed, 8 Mar 2000 14:43:10 +0100 (MET)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Dear Colleagues,
I have set up a WEB-page for PSSL 73 in Braunschweig on April 29/30
with a provision for online registration. Eventually, further details
about the meeting will appear there. It is located at
http://www.iti.cs.tu-bs.de/~koslowj/PSSL73.html
Those of you, who have already registered, of course don't have to do
so again.
-- J"urgen Koslowski
--
J"urgen Koslowski If I don't see you no more on this world
ITI, TU Braunschweig I'll meet you on the next one
koslowj@iti.cs.tu-bs.de and don't be late!
http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR)
From rrosebru@mta.ca Sun Mar 5 11:48:07 2000 -0400
Date: Sun, 5 Mar 2000 11:48:07 -0400 (AST)
From: Bob Rosebrugh
To: categories
Subject: BOUNCE categories@mta.ca: Approval required: (fwd)
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Status: RO
X-Status:
Approved: tcas
>From rrosebru Sat Mar 4 22:36:10 2000
Received: from zent.mta.ca (zent.mta.ca [138.73.101.4])
by mailserv.mta.ca (8.9.3/8.9.3) with SMTP id WAA07262
for ; Sat, 4 Mar 2000 22:36:10 -0400 (AST)
Received: FROM kestrel.kestrel.edu BY zent.mta.ca ; Sat Mar 04 22:37:02 2000
Received: from brant.kestrel.edu (brant.kestrel.edu [206.159.212.32])
by kestrel.kestrel.edu (8.9.3/8.9.3) with ESMTP id SAA10181;
Sat, 4 Mar 2000 18:36:01 -0800 (PST)
Received: from kestrel.edu (blackbird.kestrel.edu [206.159.212.151])
by brant.kestrel.edu (8.9.3/8.9.3) with ESMTP id SAA24249;
Sat, 4 Mar 2000 18:35:58 -0800 (PST)
Message-ID: <38C1C83C.A6DCAC6E@kestrel.edu>
Date: Sat, 04 Mar 2000 18:36:44 -0800
From: Dusko Pavlovic
X-Mailer: Mozilla 4.5 [en] (Win98; U)
X-Accept-Language: en,nl
MIME-Version: 1.0
To: Adam Eppendahl
CC: categories@mta.ca
Subject: Re: categories: dom fibration
References: <200003032128.VAA02592@bruno.dcs.qmw.ac.uk>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
> Can anyone explain why the codomain fibration cod: C^\rightarrow -> C,
> which requires pull-backs, gets loads of attention, while the domain
> fibration dom: C^rightarrow -> C, which works for all C, hardly gets a
> look in? Is the dom fibration really such a poor relation?
heh, the amount of attention is not always proportional to the depth of
the issue. but in this case, i think, there are good reasons for
asymmetry.
the idea of fibred (or indexed) category theory over, say, a base S, is
that each category C is always given together with all categories C^I of
I-indexed families from C, where I are the objects of S. indeed, ordinary
categories are always given with their set indexed versions. we are
tacitly using C^2 to say "product". joining all such indexed versions of C
as the fibres, we get the fibred presentation of C, its "externalization".
but now, the base category S itself should come about as an object of
category theory over S as well. in ordinary category theory, we often
mention the category of sets. the base fibration cod: Ar(S) --> S is the
externalization of S itself as fibred over S. indeed, its fibres, the
slices S/I are the abstract categories of I-indexed families from S. when
S is Set, they are equivalent to S^I; but the latter may not exist for a
general S. the pullbacks in S correspond to reindexing within S. if there
is no reindexing, then S is a poor base for category theory, because it
cannot even reindex itself.
however, even the categories S that cannot reindex themselves, they can
always comprehend themselves (in a formal sense of categorical
psychology). this is expressed by the functor dom: Ar(S)-->S. whether cod
is a fibration or not, there is always the adjunction cod -| ids -| dom:
Ar(S) -->S, which is the categorical form of the comprehension scheme, as
studied by Lawvere and later others, who generalized the adjunction
requirements away, so that the conceptual link with the set theoretical
idea of comprehension got lost...
in any case, if you embed CAT_S--->FIB/S, then cod: Ar(S)-->S is the image
of S itself, while dom: Ar(S)-->S is not in the image of the embedding,
but a derived concept.
-- dusko
From rrosebru@mta.ca Wed Mar 8 17:16:15 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id LAA13906
for categories-list; Wed, 8 Mar 2000 11:39:00 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Mailer: exmh version 2.0.2 2/24/98
To: categories@mta.ca
Subject: categories: 2nd CFP:LICS Workshop on Chu Spaces and Applications 25th June 2000
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
From: Valeria Correa Vaz de Paiva
Message-Id: <00Mar6.162559pdt."79836"@panini.parc.xerox.com>
Date: Mon, 6 Mar 2000 16:26:27 PST
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
As usual, apologies for multiple copies!!
SECOND CALL FOR PAPERS
LICS'2000 Workshop on
Chu Spaces: Theory and Applications
Sunday, June 25, 2000, Santa Barbara, California
http://www.cs.bham.ac.uk/~vdp/chu.html
A Chu space is a related pair of complementary objects.
Besides having intrinsic interest in their own right, Chu spaces
have found applications to concurrent processes, information flow,
linear logic, proof theory, and universal categories. The workshop is
concerned with the theory and applications of Chu spaces, as well as
related structures such as the Dialectica construction and double glueing.
The workshop will bring together computer scientists, mathematicians,
logicians, philosophers, and other interested parties to discuss the
development of the subject with regard to its foundations, applications,
prospects, and directions for future work. Work in the subject is
currently fragmented across several areas: category theory, traditional
model theory, concurrency, and the semantics of programming languages,
and such a workshop can contribute to the coordination and possibly even
some unification of these efforts.
Suggested topics for presentation and discussion include but are by no
means limited to new results about Chu spaces and related structures;
their applications to various areas such as concurrency, games, proof
theory, etc.; and their implications for foundations and philosophy of
computation, mathematics, physics, and other disciplines.
The workshop will be held on Sunday, June 25, 2000 at Santa Barbara,
California, as an adjunct to the International Conference on Logic in
Computer Science (LICS'2000), June 26-29 at the same location as per
http://www.cs.bell-labs.com/who/libkin/lics/index.html.
Papers within the scope of the workshop are solicited, and may be either
work in progress or more mature work. Submission should be in the form
of an extended abstract of at most 10 pages, in postscript format, mailed
electronically to paiva@parc.xerox.com. Submissions will be evaluated
by a committee selected by the organizers, and the full version of
accepted papers will be printed in a proceedings available at the start
of the workshop.
Important dates:
Extended abstract: April 25, 2000
Notification of acceptance: May 15, 2000
Proceedings version: June 9, 2000
The workshop will be one full day and is open to all interested
researchers.
Valeria de Paiva paiva@parc.xerox.com
Vaughan Pratt pratt@cs.stanford.edu
http://www.cs.bham.ac.uk/~vdp/chu.html
From rrosebru@mta.ca Mon Mar 13 16:40:05 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id OAA32409
for categories-list; Mon, 13 Mar 2000 14:12:51 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <38CD28E6.8443497C@yorku.ca>
Date: Mon, 13 Mar 2000 12:44:10 -0500
From: jwpell
X-Mailer: Mozilla 4.7 (Macintosh; U; PPC)
X-Accept-Language: en
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: AMS special session: Toronto
Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353"
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
As you may be aware, the AMS is holding a regional meeting (#957 ) in
Toronto September 22-24, 2000. Walter Tholen and I are organizing a
special session in that meeting entitled Applied Categorical Structures.
We hope you can attend.
The preliminary list of speakers includes: Lars Birkedal, Marta Bunge,
Robin Cockett, Jack Duskin, Andre Joyal, Jim Lambek, Bill Lawvere, Michael
Makkai, Bob Pare, Jiri Rosicky, Myles Tierney, Enrico Vitale, and Richard
Wood.
There will be time in total for 20 lectures of approximately 25 minutes
duration. We would be happy to receive proposals for additional talks to
complete our list. The AMS encourages expository talks in special
sessions. If you would like to speak, please send us at this time a title
or brief desciption of your proposed talk. If we are able to include you
as a speaker, you will have to provide an abstract to be printed in the
appropriate issue of the AMS journal Abstracts. We will inform you of the
particulars later.
Unfortunately, the AMS does not provide financial assistance to any of
those participating in the special sessions. We hope this will not be an
impediment to your participation. We expect to make the meeting a pleasant
one by organizing at least one social function.
--
Dr. Joan Wick Pelletier
Department of Mathematics and Statistics
York University
From rrosebru@mta.ca Wed Mar 15 13:58:14 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id MAA26068
for categories-list; Wed, 15 Mar 2000 12:09:15 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id:
To: categories@mta.ca
Subject: categories: Compact Categories
Mime-Version: 1.0 (generated by tm-edit 7.108)
Content-Type: text/plain; charset=US-ASCII
Date: Wed, 15 Mar 2000 15:14:02 +0000
From: N Ghani
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
I would like some recommended papers to read about compact
categories. Preferably accesible over the web for ease of getting hold
of. In particular,
- From a computational point of view, what are the arguments for and
against having such structure
- Examples of categories which are compact
- In Set, can we describe the relationship between initial algebras
and final coalgebras
Neil
From rrosebru@mta.ca Wed Mar 15 14:04:10 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id MAA29717
for categories-list; Wed, 15 Mar 2000 12:10:15 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: bocoecke@vub.ac.be (Coecke Bob)
Message-Id: <200003151524.QAA14526@mach.vub.ac.be>
Subject: categories: Category Theory Symposium
To: categories@mta.ca
Date: Wed, 15 Mar 2000 16:24:13 +0100 (MET)
CC: Coecke Bob
X-Mailer: ELM [version 2.4ME+ PL66 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Dear Colleagues,
We announce a "PSSL-like" meeting on category theory in Brussels,
April 8-9. Please check out our webpage for participants and
program (there is still space for some more lectures):
http://www.vub.ac.be/CLEA/BobWS2000.html
Note that the week after we have a workshop on quantum logic
focussed on applications of quantales and categorical methods,
outlined on the same webpage.
For confirmation of participation or other information, we are
Bob Coecke - bocoecke@vub.ac.be
Isar Stubbe - i.stubbe@agel.ucl.ac.be
Yours sincerely.
--
Bob Coecke, Foundations of Exact Sciences (FUND),
Department of Mathematics, Free University of Brussels,
Tel: ++32/2/629.34.99; Fax: ++32/2/629.34.95
http://www.vub.ac.be/CLEA/BobCoecke.html
From rrosebru@mta.ca Wed Mar 15 14:19:06 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA13309
for categories-list; Wed, 15 Mar 2000 09:39:06 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Paul Taylor
Date: Wed, 15 Mar 2000 13:11:31 GMT
Message-Id: <200003151311.NAA15811@koi-pc.dcs.qmw.ac.uk>
To: categories@mta.ca
Subject: categories: gluing, lifting and partial maps
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
I have long regarded it as "well known" that
the partial map classifier for topological spaces or locales
where
by "partial" I mean a continuous function defined on an open subset
is
the Artin gluing, Freyd cover or scone (Sierpinski cone).
Can anybody point me to a published proof of this, or even tell me who
first proved it?
The same construction, with frames replaced by the categories of contexts
and substitutions (a.k.a. classifying categories) for theories in other
fragments of logic, has also been used with spectacular results to prove
consistency, strong normalisation, etc. I know of plenty of work on
that application itself, but I wonder whether anybody has investigated
the connection between these two applications of the construction.
Paul
PS Thanks to everyone who wrote to me about 1970s calculators. I will be
writing back and summarising the responses for "categories" after the end
of term. When the students have sat my exam paper (sometime in May)
I will also post to "categories" the actual question that I composed.
From rrosebru@mta.ca Wed Mar 15 15:31:11 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA08334
for categories-list; Wed, 15 Mar 2000 08:25:34 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <004001bf8e66$ace413a0$cf85fea9@tmp-sabadini.fis.unico.it>
From: "RFC Walters"
To:
Subject: categories: Extended deadline CT 2000
Date: Wed, 15 Mar 2000 11:09:49 +0100
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 4.72.3110.5
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
X-MIME-Autoconverted: from 8bit to quoted-printable by grus.promo.it id LAA14426
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id GAA00916
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
EXTENSION OF DEADLINE FOR SUBMISSION OF ABSTRACTS
The deadline for submissions to CT 2000 has been extended to
22nd March 2000. Email adress for the submission of abstracts is
ct2000@disi.unige.it.
Please email of your intention to submit by the 17th March.
REGISTRATION
Registration for the conference is now possible by consulting the web page
http://www.disi.unige.it/conferences/ct2000/.
The registration fee is Lit.250000, reduced to Lit.180000 for students.
Also consider that the conference dinner will be on Wednesday, July 19, and
the cost of a dinner ticket is Lit.70000.
----------------------------------------------------------------------------
---
CALL FOR PAPERS
CATEGORY THEORY 2000 (CT 2000)
July 16-22, 2000
Centro di Cultura Scientifica
"Alessandro Volta"
di Villa Olmo
Como, Italy
The next international summer conference in category theory will be held at
Villa Olmo from Sunday 16th July to Saturday 22nd July 2000. We invite
submissions in all areas of category theory and its applications, but
particularly in the following areas:
* algebraic topology and homological algebra,
* categorical logic,
* categories and computer science,
* enriched category theory and 2-dimensional universal algebra,
* galois theory and descent,
* general category theory.
* higher dimensional category theory and quantum algebra,
* topos theory and synthetic differential geometry,
The web page for the conference is
http://www.disi.unige.it/conferences/ct2000/
Electronic submissions are preferred but authors may instead mail 4 copies
of an extended abstract, in either case to arrive by 15th March, 2000.
Email address for electronic submissions
ct2000@disi.unige.it
Mail address for hardcopy submissions
RFC Walters
(CT 2000)
Dipartimento di Scienze CC., FF., MM.,
Università degli studi dell'Insubria
22100 Como,
Italy
Important Dates
22nd March, 2000: Papers due (extended deadline)
15 May, 2000: Notification of acceptance or rejection of papers
16-22 July, 2000: Conference
Papers should be submitted in the form of an extended abstract. Papers
should begin with the title of the paper, each author's name, affiliation,
and e-mail address, followed by a statement as to which of the areas
of category theory mentioned above the paper belongs, a succinct
statement of the problems and goals that are considered in the paper,
the main results achieved, the significance of the work in the
context of previous research, and a comparison to past research.
The abstract should provide sufficient detail to allow the program committee
to evaluate the validity, quality, and relevance of the contribution.
The entire extended abstract should not exceed 10 pages.
Authors will be notified of acceptance or rejection by 15 May, 2000.
Program Committee
S.L. Bloom (Stevens Institute, USA)
J.M.E. Hyland (Cambridge, U.K.)
G. Janelidze (Tbilisi, Georgia)
G.M. Kelly (Sydney, Australia)
A. Kock (Aarhus, Denmark)
I. Moerdijk (Utrecht, The Netherlands)
R. Paré (Dalhousie, Canada)
R.H. Street (Macquarie, Australia)
Organizing Committee
A. Carboni (Insubria)
G. Rosolini (Genova)
R.F.C. Walters (Insubria and Sydney)
15th March 2000
From rrosebru@mta.ca Wed Mar 15 18:12:47 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id QAA23124
for categories-list; Wed, 15 Mar 2000 16:13:47 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <38CFC7CA.6F3029CD@bangor.ac.uk>
Date: Wed, 15 Mar 2000 17:26:34 +0000
From: Ronnie Brown
X-Mailer: Mozilla 4.6 [en-gb] (Win98; I)
X-Accept-Language: en-GB,en,en-*
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Re: gluing, lifting and partial maps
References: <200003151311.NAA15811@koi-pc.dcs.qmw.ac.uk>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Abd-Allah and I dealt with this in
``A compact-open topology on partial maps with open domain'', {\em J. London
Math Soc.} (2) 21 (1980) 480-486.
as a development of work with Peter Booth in
``Spaces of partial maps, fibred mapping spaces and the compact-open
topology'', {\em Gen. Top. Appl.} 8 (1978) 181-195.
We got the idea of representability of partial maps from Peter Freyd's
article on topos theory. Is there an earlier result on these lines?
Ideas on making spaces over B into a Cartesian closed category came initially
from a paper of Rene Thom, and were developed in Peter's work at Hull. This
eventually suggested the topologisation of spaces of partial maps as a step
towards Top/B.
Ronnie Brown
Paul Taylor wrote:
> I have long regarded it as "well known" that
> the partial map classifier for topological spaces or locales
> where
> by "partial" I mean a continuous function defined on an open subset
> is
> the Artin gluing, Freyd cover or scone (Sierpinski cone).
>
> Can anybody point me to a published proof of this, or even tell me who
> first proved it?
>
> The same construction, with frames replaced by the categories of contexts
> and substitutions (a.k.a. classifying categories) for theories in other
> fragments of logic, has also been used with spectacular results to prove
> consistency, strong normalisation, etc. I know of plenty of work on
> that application itself, but I wonder whether anybody has investigated
> the connection between these two applications of the construction.
>
> Paul
>
> PS Thanks to everyone who wrote to me about 1970s calculators. I will be
> writing back and summarising the responses for "categories" after the end
> of term. When the students have sat my exam paper (sometime in May)
> I will also post to "categories" the actual question that I composed.
From rrosebru@mta.ca Fri Mar 17 09:45:12 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA19202
for categories-list; Fri, 17 Mar 2000 09:35:07 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200003171150.MAA06434@fennec.inria.fr>
X-Mailer: exmh version 2.0.2 2/24/98
To: categories@mta.ca
Subject: categories: Applied Semantics Summer School
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Date: Fri, 17 Mar 2000 12:50:32 +0100
From: Simao Desousa
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id HAA16660
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Dear Colleagues,
I apologize if you receive multiple copies of this message
and would be grateful if you could distribute the 2nd Summer School
Call For Participation given below
Best regards,
S. Sousa
----------------------------------------------------------------------
2nd C A L L F O R P A R T I C I P A T I O N
------------------------------------------------
INTERNATIONAL SUMMER SCHOOL
ON APPLIED SEMANTICS
---APPSEM'2000---
Caminha, Portugal, 9-15 September 2000
http://www-sop.inria.fr/oasis/Caminha00/index.html
OBJECTIVE AND BACKGROUND
Programming languages are the basic tools with which all applications
of computers are built. It is important, therefore, that they should
be well designed and well implemented. Achieving these goals requires
both a good theoretical understanding of programming language designs,
and practical skills in the development of high quality compilers.
The summer school is addressed to postgraduate students, researchers
and industrials who want to learn about recent developments in programming
language research, both in semantic theory and in implementation.
The programme will consist of introductory and advanced courses on the
following themes:
- description of existing programming language features;
- design of new programming language features;
- implementation and analysis of programming languages;
- transformation and generation of programs;
- verification of programs.
LOCATION
The summer school is located in Caminha, a picturesque village by the
sea and on the Rio Minho, on the northern border between Portugal and
Spain.
PROGRAMME
- Andrew Pitts, Cambridge University.
Operational Semantics.
- John Hughes, Chalmers University, Eugenio Moggi, Genova University,
and Nick Benton, Microsoft Research.
Monads and Effects.
- Pierre-Louis Curien, CNRS and Paris 7 University.
Games and Abstract Machines.
- Thierry Coquand, Chalmers University, and Gilles Barthe, INRIA.
Dependent Types in Programming.
- Olivier Danvy, BRICS and Peter Dybjer, Chalmers University.
Normalization and Partial Evaluation.
- Cédric Fournet, Microsoft Research and Georges Gonthier, INRIA.
Join Calculus: a model for distributed programming.
- Xavier Leroy, INRIA, and Didier Rémy, INRIA.
Objects, Classes and Modules in Objective CAML.
- Martin Odersky, Ecole Polytechnique Federale de Lausanne.
Functional Nets.
- Abbas Edalat, Imperial College, and Achim Jung, Birmingham University.
Exact Real Number Computation.
REGISTRATION
The registration fees covers proceedings, full boarding, refreshments,
social events and a banquet:
- early registration (before April 21st)
* single room: 120 000 PTE
* double room: 100 000 PTE
- late registration
* single room: 140 000 PTE
* double room: 120 000 PTE
There is no deadline for late registration but accommodation is not
guaranteed if you applied after the 1st July 2000.
See http://www-sop.inria.fr/oasis/Caminha00/registration.html for
further information.
GRANTS
Limited funds will be available for grants. The deadline for
application for a grant is April 1st. You will receive notification of
acceptance/rejection by April 8th.
To apply for a grant, see http://www-sop.inria.fr/oasis/Caminha00/grant.html.
FURTHER INFORMATION
For further information, please contact the organizing committee by
email (appsem-school@di.uminho.pt).
From rrosebru@mta.ca Mon Mar 20 10:42:38 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id KAA23800
for categories-list; Mon, 20 Mar 2000 10:32:20 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Mon, 20 Mar 2000 09:41:59 -0400 (AST)
From: Bob Rosebrugh
To: categories
Subject: categories: Graphical Database for Category Theory (GDCT)
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
We announce the availability of a Java application for storage and display
of finitely presented categories and functors among them.
The application is available for download at
http://mathcs.mta.ca/research/rosebrugh/gdct/
and is also linked from
http://www.mta.ca/~rrosebru/
For Win9x/NT users, a single download provides the application along with
the required Java run-time environment. Installation is via InstallShield.
For other operating systems, download the Java archive for the application
and, separately, the appropriate Java run-time environment (to which
links are provided).
We are interested in any response from users, and in expanding the
database of categories and functors available from the default server, so
we would be happy to receive examples from users. It is intended to
upgrade the application this summer, and so we would also appreciate
receiving any reports of difficulties in function or usability, as well as
suggestions for new functionality.
The application allows for the creation, editing, display and storage of
finitely presented categories. Categories can be opened and saved from
local files as well as loaded from a specified server. Open categories can
be displayed graphically, and the graphical display can be manipulated (in
3 dimensions) and stored. Several tools for testing properties of objects
and arrows can be applied; in this version they include Make Confluent,
Equality of Composities, Make Dual, Initial Object, and Terminal Object.
Functors between stored categories can also be created and stored. Open
functors can be displayed and animated.
A built-in help system describes how to use the application.
Graphical Database for Category Theory was developed in the summer of 1999
by Jeremy Bradbury and R. Rosebrugh with support from an NSERC Canada
undergraduate summer research assistantship.
Some of the algorithms used in GDCT were originally developed in A
Database of Categories, a C program written by Ryan Gunther and Michael
Fleming, and Category Theory Database Tools a Java applet, written by
Jeremy Bradbury, both under the supervision of R. Rosebrugh.
We hope that some of you will find GDCT useful and enjoyable.
Bob Rosebrugh and Jeremy Bradbury
From rrosebru@mta.ca Tue Mar 21 12:47:16 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA04380
for categories-list; Tue, 21 Mar 2000 08:20:20 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 21 Mar 2000 11:58:03 GMT
Message-Id: <12426.200003211158@craro.dcs.ed.ac.uk>
To: categories@mta.ca
Subject: categories: CTCS '99 Special Issue in TCS. Final Reminder.
From: "Martin Hofmann"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Call for Papers
Special Issue of
Theoretical Computer Science (TCS)
on
Categories in Computer Science
Editors: J. Adamek, M. Escardo, M. Hofmann
The eighth conference on Category Theory and Computer Science
(CTCS'99) has been held in Edinburgh 10-12 September 1999.
A special issue of the journal Theoretical Computer Science (TCS) will
be devoted to journal versions of papers presented at that conference
and other papers on the same topic.
Submissions will undergo the usual refereeing process for TCS; authors
of submissions are not required to have participated at CTCS'99.
>From the call for papers: "The purpose of the conference series is the
advancement of the foundations of computing using the tools of
category theory. While the emphasis is upon applications of category
theory, it is recognized that the area is highly
interdisciplinary. Topics of interest include but are not limited to
category-theoretic aspects of the following:
concurrent and distributed systems, constructive mathematics,
declarative programming and term rewriting, domain theory and
topology, linear logic, models of computation, program logics, data
refinement, and specification, programming language semantics, type
theory".
See also http://www.dcs.ed.ac.uk/home/ctcs99 for the conference
programme.
Instructions to Authors
-----------------------
Authors are invited to submit full original research papers. Papers
should be submitted via email to ctcs99@dcs.ed.ac.uk as a postscript
file, or by mailing a hard copy to
Martin Hofmann
Laboratory for Foundations of Computer Science
JCM, Rm 2606
The King's Buildings
Mayfield Rd
Edinburgh EH9 3JZ
UK
before 31st March, 2000.
Authors who would like to submit a paper but feel that the deadline is
too tight should contact me by email (mxh@dcs.ed.ac.uk) before the
deadline. An extension could then be negotiated.
From rrosebru@mta.ca Tue Mar 21 12:44:05 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA06408
for categories-list; Tue, 21 Mar 2000 08:19:25 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <20000321032140.16960.qmail@hotmail.com>
X-Originating-IP: [207.46.125.17]
From: "Bill Halchin"
To: categories@mta.ca
Subject: categories: RFC Walters' book
Date: Mon, 20 Mar 2000 19:21:40 PST
Mime-Version: 1.0
Content-Type: text/plain; format=flowed
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Hello,
Is this a good/appropriate forum to ask questions about RFC
Walters' "Categories and Computer Science". In particular I don't
understand the beginning of Chapter 6. I.e. The Free Category With
Products.
Regards,
Bill Halchin
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com
From rrosebru@mta.ca Tue Mar 21 19:22:48 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id OAA14929
for categories-list; Tue, 21 Mar 2000 14:30:43 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Jiri Adamek
Message-Id: <200003211248.NAA10012@lisa.iti.cs.tu-bs.de>
Subject: categories: Preprint: a paper on injective hulls
To: categories@mta.ca
Date: Tue, 21 Mar 2000 13:48:02 +0100 (MET)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
This is to announce a paper that can be obtained as "Paper3-2000.ps"
on the address ftp://ftp.iti.cs.tu-bs.de/pub/staff/adamek
TITLE: Injective Hulls are not Natural
AUTHORS: J. Adamek, H. Herrlich, J. Rosicky and W. Tholen
ABSTRACT: In a category with injective hulls and a cogenerator, the
embeddings into injective hulls can never form a natural transformation,
unless all objects are injective. In particular, assigning to a field
its algebraic closure, to a poset or boolean algebra its MacNeille
completion, and to an R-module its injective envelope is not functorial,
if one wants the respective embeddings to form a natural transformation.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
alternative e-mail address (in case reply key does not work):
J.Adamek@tu-bs.de
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
From rrosebru@mta.ca Tue Mar 21 19:54:05 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id TAA07560
for categories-list; Tue, 21 Mar 2000 19:53:56 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 21 Mar 2000 16:32:09 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: Topos theory and large cardinals
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Andrej Bauer asked whether large cardinals other than inaccessible ones
have a natural definition in topos theory. Indeed, like most questions
of set theory which have an objective content, this too is independent
of the a priori global inclusion and membership chains which are
characteristic of the Peano conception that ZF formalizes. Various kinds
of "measurable" cardinals arise as possible obstructions to simple
dualities of the type considered in algebraic geometry. Actually,
measurable cardinals are those which canNOT be measured by smaller ones,
because of the existence on them of a type of homomorphism which is
equivalent to the existence of a measure in the sense of Ulam.
Specifically, let V be a fixed object and let M denote the monoid object
of endomorphisms of V. Then the contravariant functor ( )^V is actually
valued in the category of left M-actions and as such has an adjoint which
is the enriched hom of any left M-set into V. The issue is whether the
composite of these, the double dualization, is isomorphic to the identity
on the topos; if so, one may say that all objects are measured by V, or
that there are no objects supporting non-trivial Ulam elements. In any
case, the double dualization monad obtained by composing seems to add new
ideal Ulam elements to each object, i.e. elements which cannot be nailed
down by V-valued measurements. Since fixed points for the monad are
special algebras, and since algebras are always closed under products
etc., it should be possible to devise a very natural proof based on monad
theory that the category of these non-Ulam objects is itself a topos and
even "inaccessible" relative to the ambient topos.
Why is the above definition relevant? The first example should be
the topos of finite sets with V a three-element set. There the monad is
indeed the identity, as can be seen by adapting results of Stone and Post.
Extending the same monad to infinite sets, we obtain the Stone-Czech
compactification beta.
The key example is a topos of sets in which we have V a fixed
infinite set. As Isbell showed in 1960, the category contains no Ulam
cardinals in the usual sense if and only if the monad described above is
the identity.
Further examples involve the complex numbers as V, where actually M
can be taken to consist only of polynomials, with the same result; this
example extends nicely from discrete sets to continuous sets, usually
discussed in the context of "real compactness". Another kind of example
concerns bornological spaces. The result always seems to be that the lack
of Ulam cardinals is equivalent to the exception-free validity of basic
space/quantity dualities.
Ulam (and other set theorists since) usually in effect phrase the
construction in terms of a two-element set V equipped however with
infinitary operations. Isbell's remark shows that equivalently an
infinite set equipped with finitary (indeed only unary) operations can
discern the same distinctions between actual elements as values of the
Dirac-type adjunction map and ghostly Ulam elements on the other hand.
*****************************************************************
F. William Lawvere
Mathematics Dept. SUNY Buffalo, Buffalo, NY 14214, USA
716-829-2144 ext. 117
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
*****************************************************************
From rrosebru@mta.ca Wed Mar 22 10:08:29 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id KAA24610
for categories-list; Wed, 22 Mar 2000 10:03:06 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <004b01bf93f5$190323d0$24001e0a@itc.it>
From: "Carola Dori"
To: categories@mta.ca
Subject: categories: AIPS2000 Workshop on Model-Theoretic Approaches to Planning: Preliminary Programme
Date: Wed, 22 Mar 2000 12:52:16 +0100
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2014.211
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
The time schedule is still preliminary and has to be decided with the
AIPS2000 organizers!
--------------------------------------------------------------------------
AIPS2000 Workshop on
Model-Theoretic Approaches to Planning:
Preliminary Programme
--------------------------------------------------------------------------
8.30 - 9.30 Invited Talk:
Automated Verification = Graphs, Automata, and Logic
(Moshe Y. Vardi)
9.30 - 10.00 Using Model Checking to Plan Hard Real-Time Controllers
(R.P. Goldman, D.J. Musliner, M.J. Pelican)
10.00 - 10.15 Coffee Break
10.15 - 10.45 Propositional planning
(M.P. Fourman)
10.45 - 11.15 On the Implementation of MIPS
(S. Edelkamp and M. Helmert)
10.15 - 11.45 OBDD-based Deterministic Planning using the UMOP
Planning Framework
(R.M. Jensen, M.M Veloso)
11.45 - 12.15 Solving the entailment problem in the fluent calculus
using Bynary Decision Diagrams (Extended Abstract)
(S. Hoelldobler and P. Stoerr)
12.15 - 2.00 Lunch
2.00 - 3.00 Invited Talk:
Planning with State Models, MDPs and POMDPs:
A general framework for planning and control in AI
(Hector Geffner)
3.00 - 3.15 Coffee Break
3.15 - 3.45 Forward conformant Planning via symbolic model checking
(A. Cimatti, M. Roveri)
3.45 - 4.15 ZANDER: A model theoretic approach to planning in
partially observable stochastic domains
(S. Majerci and M. Littman)
4.15 - 4.45 Planning as Satisfiability in simple
nondeterministic domains
(P. Ferraris, E. Giunchiglia)
4.45 - 5.15 Planning with Domain and Control Knowledge in
Linear Time Logic
(M. Cialdea Meyer,A. Orlandini,G. Balestreri,C.
Limongelli)
5.15 - 5.30 Conclusions
--------------------
INVITED TALK:
Automated Verification = Graphs, Automata, and Logic
Moshe Y. Vardi
Rice University
In automated verification one uses algorithmic techniques to
establish the correctness of the design with respect to a given
property. Automated verification is based on a small number of
key algorithmic ideas, tying together graph theory, automata
theory, and logic. In this self-contained talk I will describe how
this "holy trinity" gave rise to automated-verification tools.
--------------------
INVITED TALK:
Planning with State Models, MDPs and POMDPs:
A general framework for planning and control in AI
Hector Geffner
Depto de Computacion
Universidad Simon Bolivar
Caracas, Venezuela
We consider the problem of planning in a general setting
where actions can be deterministic, non-deterministic, or probabilistic,
and their effects can be fully or partially observable. The task is to
obtain
a plan or closed-loop controller given a suitable description
of the initial situation, actions, sensors, and goals.
We approach this problem by distinguishing three elements:
- models (that help us to make the tasks mathematically precise)
- languages (that help us to state problems in a convenient way), and
- algorithms (that compute the desired solutions: plans, controllers, etc.)
We show that the models - State Models, Markov Decision Processes (MDPs)
and Partially Observable MDPs - can be conveniently described using
suitable logical action languages, and in many cases can be solved
by search algorithms that combine ideas from heuristic search and
dynamic programming. We also present some empirical results,
and discuss limitations and challenges.
This is joint work with Blai Bonet.
---------------------------------------
From rrosebru@mta.ca Wed Mar 22 10:25:12 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id KAA07332
for categories-list; Wed, 22 Mar 2000 10:23:08 -0400 (AST)
Message-Id: <200003220938.SAA00930@cssol032.kyoto-su.ac.jp>
X-Authentication-Warning: cssol032.kyoto-su.ac.jp: esik@localhost didn't use HELO protocol
To: categories@mta.ca
Subject: categories: FICS 2000, change in submission guidleines
Date: Wed, 22 Mar 2000 18:38:21 +0900
From: esik (researcher;Itou Masami)
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Please note the change in the submission guidelines.
FIXED POINTS IN COMPUTER SCIENCE (FICS 2000) July 22-23, 2000, Paris, France
Call for Papers: http://www.liafa.jussieu.fr/~ig/FICS.html
* Fixed points play a fundamental role in several areas of computer
science and logic by justifying induction and recursive definitions.
The construction and properties of fixed points have been investigated
in many different frameworks. The aim of the workshop is to provide a
forum for researchers to present their results to those members of the
computer science and logic communities who study or apply the fixed point
operation in the different fields and formalisms.
* Invited speakers: S. Bloom, B. Courcelle, H. Marandjian, J. Rutten,
I. Walukiewicz.
* Paper submission: Electronic submissions in the form
of uuencoded postscript file are encouraged and should be sent
in duplicate to ***both***
ig@liafa.jussieu.fr **and** esik@inf.u-szeged.hu
Authors can also send 3 copies of an abstract
not exceeding 3 pages to the PC chair.
Submissions are to be received before April 3, 2000.
Authors will be notified of acceptance by June 1, 2000.
From rrosebru@mta.ca Wed Mar 22 17:03:12 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id QAA21675
for categories-list; Wed, 22 Mar 2000 16:24:37 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 22 Mar 2000 15:17:14 -0500 (EST)
From: Peter Freyd
Message-Id: <200003222017.PAA15701@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: Functorial injective hulls
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
Some comments on:
>TITLE: Injective Hulls are not Natural
>AUTHORS: J. Adamek, H. Herrlich, J. Rosicky and W. Tholen
>ABSTRACT: In a category with injective hulls and a cogenerator, the
>embeddings into injective hulls can never form a natural transformation,
>unless all objects are injective. In particular, assigning to a field
>its algebraic closure, to a poset or boolean algebra its MacNeille
>completion, and to an R-module its injective envelope is not functorial,
>if one wants the respective embeddings to form a natural transformation.
What is meant by saying that an object is "injective" varies a bit
from place to place. If it means that the object represents a
contravariant functor that carries monics into epics and if one defines
an "injective hull" of an object A to mean
a monic A --> E where E is injective and such that
A --> E --> X monic implies E --> X is monic
then there are non-trivial examples of functorial injective hulls: take
any poset with a top element and view it as a category; the only
injective object is the top and the unique map from any object to the
top is easily verified to be an injective hull.
Apparently, therefore, the meaning of injective is a mutation obtained
by changing the word "monic" in the above description to something
stronger, such as "extremal monic" or "regular monic". (In Cats and
Alligators the notions of projective and injective are not dual: a
co-projective would be the mutation of injective obtained by using
extremal monics.)
If the strengthening of monic is such that it becomes an iso whenever
epic (as is the case with extremal and regular), then there's an easy
proof of the impossibility of functoriality, with or without a
cogenerator.
In the days when all categories were abelian (that is, in the days
when people actually talked about injective hulls) it was also the
case that all monic-epics were isos, and this easy proof was a pretty
standard exercise. It goes as follows. Suppose that E is a functor,
u a natural transformation from the identity functor to E such that
u:A --> E(A) is an injective hull for all A. We wish to show that u
is epic.
If B is injective then there must be E(B) --> B such that
B --> E(B) --> B is the identity map. The definition of injective
hull forces E(B) --> B to be monic which, in turn, forces u_B to
be an iso. We may replace E with a naturally equivalent functor with
the property that u_B is the identity map whenever B is injective.
For an arbitrary A consider
u
A ---> E(A)
u | | E(u)
1
E(A) --> E(A)
E(u) | | E(u)
1
E(A) --> E(A)
and conclude that E(u) is an idempotent. Using again (and for the
last time) the definition of injective hull we have that E(u) is
monic. The only monic idempotent is the identity map.
u x u y
Suppose that A --> E(A) --> C = A --> E(A) --> C. Consider
u u
A ---> E(A) A ---> E(A)
u | | 1 u | | 1
1 1
E(A) --> E(A) E(A) --> E(A)
x | | E(x) y | | E(y)
u u
C ---> E(C) C ---> E(C)
If one considers just the outer rectangles one sees that the left hand
verticals are the same, hence so must be the right hand verticals.
But u is monic, thus E(x) = E(y) implies x = y.
From rrosebru@mta.ca Thu Mar 23 13:57:15 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id NAA21202
for categories-list; Thu, 23 Mar 2000 13:54:38 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: "Walter Tholen"
Message-Id: <1000322181057.ZM23382@pascal.math.yorku.ca>
Date: Wed, 22 Mar 2000 18:10:57 -0500
X-Mailer: Z-Mail (4.0.1 13Jan97)
To: categories@mta.ca
Subject: categories: Re: Functorial injective hulls
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Peter,
Jirka Adamek had prepared a draft response to your earlier remark that a poset
with top element should disprove the assertion in the Abstract of our paper
(with Herrlich and Rosicky) which he had circulated. His response is attached
below, slightly edited by me - hence I take full responsibility for its
contents.
Our proof of the Theorem adds only one twist to the proof you have just
circulated: monomorphisms get substituted by an absolutely ARBITRARY class H of
morphisms; H-injective then indeed means that the contravariant hom sends H to
epis; and H-essential is as you described as well (: an h in H such that g.h is
in H only if g is in H). We are able to compensate for the loss of mono through
condition 1, while condition 2 obviously replaces your (epi&mono is iso). For
full details, please consult the paper.
Best wishes,
Walter.
=============================================================================
Dear Peter,
The precise result we prove in our paper is the following:
Theorem. Let H be a class of morphisms in a category C such that
1. all H-injective objects form a cogenerating class, and
2. the class of all H-essential morphisms which are epimorphic
is precisely the class of isomorphisms of C .
Then C cannot have natural H-injective hulls (i.e. they cannot
form an endofunctor together with a natural transformation from Id)
unless every object in C is H-injective.
The abstract we have given in our posting was meant to be an abbreviation of
this precise statement. While condition 1 holds true for the set H of all
(mono)morphisms in a poset with top element, condition 2 fails.
Best regards,
J.A., H.H., J.R., W.T.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
alternative e-mail address (in case reply key does not work):
J.Adamek@tu-bs.de
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
From rrosebru@mta.ca Fri Mar 24 04:22:49 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA15021
for categories-list; Thu, 23 Mar 2000 09:08:13 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <38D9FD66.3631F3E2@zsu.edu.cn>
Date: Thu, 23 Mar 2000 19:17:58 +0800
From: lndcs01
Reply-To: lndcs01@zsu.edu.cn
X-Mailer: Mozilla 4.6 [en] (Win98; I)
X-Accept-Language: en
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Could anyone provide me some information about enriched categories?
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
I am working on categorical model for higher-order subtyping.
I hope someone can tell me where can I find the books or papers
about insertor in enriched categories.
Thanks very much!
From rrosebru@mta.ca Fri Mar 24 04:30:44 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id VAA03867
for categories-list; Thu, 23 Mar 2000 21:47:08 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Mime-Version: 1.0
X-Sender: street@hera.mpce.mq.edu.au
Message-Id:
Date: Fri, 24 Mar 2000 11:44:28 +1100
To: categories@mta.ca
From: Ross Street
Subject: categories: Job Ad: Fwd: Daily SMARTS Output - 1 hit(s)
Content-Type: text/plain; charset="us-ascii" ; format="flowed"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
>****************************************
>Sponsor: Monash University
>Program Number: 38904
>Title: Monash University--Logan Research Fellowships
>E-mail: MaryJoy.Gleeson@adm.monash.edu.au
>Web Site: http://www.monash.edu.au/resgrant/loganfs
>
>SYNOPSIS:
> Five prestigious fellowships are awarded each year to applicants
>with two to six years of postdoctoral research experience. The
>appointment is for three years, extendible to six years, to be taken
>up by 31 December 2000. The initial salary is in the range
>A$53,844-$57,464 pa depending on experience and a Research Support
>Grant ranges from A$5,000-$20,000 pa. Return airfares are provided for
>candidates and their dependents.
>
>Deadline(s): 28/04/2000
>Link to full program description:
>http://australia.infoed.org/wConnect/wc.dll?spinwww~program~38904~BD
From rrosebru@mta.ca Fri Mar 24 04:31:45 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id QAA28382
for categories-list; Thu, 23 Mar 2000 16:30:44 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 23 Mar 2000 14:12:31 -0500 (EST)
From: Peter Freyd
Message-Id: <200003231912.OAA11052@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: More comments on Functorial injective hulls
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Some comments on:
>Theorem. Let H be a class of morphisms in a category C such that
>1. all H-injective objects form a cogenerating class, and
>2. the class of all H-essential morphisms which are epimorphic
> is precisely the class of isomorphisms of C .
>Then C cannot have natural H-injective hulls (i.e. they cannot
>form an endofunctor together with a natural transformation from Id)
>unless every object in C is H-injective.
Walter wrote "We are able to compensate for the loss of mono through
condition 1". Wouldn't it be simpler just to say that condition 1
implies that everything in H is a monomorphisms?
x y
(Let A --> B be an H-morphism and let X --> A, X --> A be such
x y
that X --> A --> B = X --> A --> B. If x were different from
y then there would be A --> E, E an H-injective object, so that
x y
X --> A --> E were different from X --> A --> E. But there would
have to be B --> E such that A --> E = A --> B --> E and
x y
X --> A --> B would have be different from X --> A --> B.)
So H-morphism is a strengthening of monic and that put's us back to
the situation I outlined:
If the strengthening of monic is such that it becomes an iso
whenever epic then there's an easy proof of the impossibility of
functoriality, with or without a cogenerator.
From rrosebru@mta.ca Fri Mar 24 04:44:33 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id QAA22968
for categories-list; Thu, 23 Mar 2000 16:31:48 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 23 Mar 2000 14:50:57 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: Re: Functorial injective hulls
In-Reply-To: <1000322181057.ZM23382@pascal.math.yorku.ca>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
But by contrast, functorial injective resolutions do exist, usually
by some sort of double-dualisation monad. What if the "hull" or minimality
requirement is imposed on the process qua functor instead of at each
object? Do such functors exist ?
*****************************************************************
F. William Lawvere
Mathematics Dept. SUNY Buffalo, Buffalo, NY 14214, USA
716-829-2144 ext. 117
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
*****************************************************************
On Wed, 22 Mar 2000, Walter Tholen wrote:
> Peter,
>
> Jirka Adamek had prepared a draft response to your earlier remark that a poset
> with top element should disprove the assertion in the Abstract of our paper
> (with Herrlich and Rosicky) which he had circulated. His response is attached
> below, slightly edited by me - hence I take full responsibility for its
> contents.
>
> Our proof of the Theorem adds only one twist to the proof you have just
> circulated: monomorphisms get substituted by an absolutely ARBITRARY class H of
> morphisms; H-injective then indeed means that the contravariant hom sends H to
> epis; and H-essential is as you described as well (: an h in H such that g.h is
> in H only if g is in H). We are able to compensate for the loss of mono through
> condition 1, while condition 2 obviously replaces your (epi&mono is iso). For
> full details, please consult the paper.
>
> Best wishes,
> Walter.
>
>
> =============================================================================
> Dear Peter,
> The precise result we prove in our paper is the following:
>
> Theorem. Let H be a class of morphisms in a category C such that
> 1. all H-injective objects form a cogenerating class, and
> 2. the class of all H-essential morphisms which are epimorphic
> is precisely the class of isomorphisms of C .
> Then C cannot have natural H-injective hulls (i.e. they cannot
> form an endofunctor together with a natural transformation from Id)
> unless every object in C is H-injective.
>
> The abstract we have given in our posting was meant to be an abbreviation of
> this precise statement. While condition 1 holds true for the set H of all
> (mono)morphisms in a poset with top element, condition 2 fails.
>
> Best regards,
> J.A., H.H., J.R., W.T.
>
>
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> alternative e-mail address (in case reply key does not work):
> J.Adamek@tu-bs.de
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
>
>
>
>
From rrosebru@mta.ca Fri Mar 24 15:16:27 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id PAA10806
for categories-list; Fri, 24 Mar 2000 15:12:34 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: "Walter Tholen"
Message-Id: <1000324140609.ZM123426@pascal.math.yorku.ca>
Date: Fri, 24 Mar 2000 14:06:09 -0500
In-Reply-To: Peter Freyd
"categories: More comments on Functorial injective hulls" (Mar 23, 2:12pm)
References: <200003231912.OAA11052@saul.cis.upenn.edu>
X-Mailer: Z-Mail (4.0.1 13Jan97)
To: categories@mta.ca
Subject: categories: Re: More comments on Functorial injective hulls
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Good point, I did not see that! So the whole thing boils down to a very simple
observation on pointed endofunctors (which is certainly well-known for
reflectors): suppose you have an endofunctor F and a natural transformation
u:Id --> F which is pointwise monic; then, if Fu is pointwise epic, u itself is
pointwise epic. Proof:
u_A x,y
A ---> FA ---> B
| | |
u_A | u_FA | | u_B
| | |
FA --> FFA --> FB
Fu_A Fx,Fy
( xu = yu gives Fx.Fu = Fy.Fu, hence Fx = Fy and then ux = uy and x = y.)
Coming back to injectivity: if u was pointwise an H-injective hull, then both
uF and Fu must be isos (independently of H being a class of monos or not!).
Hence, if H is a class of monos, the statement above applies.
> Walter wrote "We are able to compensate for the loss of mono through
> condition 1". Wouldn't it be simpler just to say that condition 1
> implies that everything in H is a monomorphisms?
> x y
> (Let A --> B be an H-morphism and let X --> A, X --> A be such
> x y
> that X --> A --> B = X --> A --> B. If x were different from
> y then there would be A --> E, E an H-injective object, so that
> x y
> X --> A --> E were different from X --> A --> E. But there would
> have to be B --> E such that A --> E = A --> B --> E and
> x y
> X --> A --> B would have be different from X --> A --> B.)
>
>
> So H-morphism is a strengthening of monic and that put's us back to
> the situation I outlined:
>
> If the strengthening of monic is such that it becomes an iso
> whenever epic then there's an easy proof of the impossibility of
> functoriality, with or without a cogenerator.
>
>-- End of excerpt from Peter Freyd
From rrosebru@mta.ca Sun Mar 26 10:07:16 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA23371
for categories-list; Sun, 26 Mar 2000 09:58:41 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Teodor Rus
Message-Id: <200003232056.OAA17039@server.divms.uiowa.edu>
Subject: categories: AMAST 2000 Call for Participation
To: categories@mta.ca
Date: Thu, 23 Mar 2000 14:56:48 -0600 (CST)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
The advance program of the AMAST 2000 is now available on the
web at the URL http://www.cs.uiowa.edu/amast2000. We hope that
this program is inciting and exciting for you and consequently
you will decide to attend this conference.
Teodor Rus
From rrosebru@mta.ca Mon Mar 27 08:23:20 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id IAA11227
for categories-list; Mon, 27 Mar 2000 08:20:50 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200003270724.RAA21218@hera.mpce.mq.edu.au>
X-Sender: mbatanin@hera.mpce.mq.edu.au
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Mon, 27 Mar 2000 18:24:57 +1100
To: categories@mta.ca
From: mbatanin@ics.mq.edu.au (Michael Batanin)
Subject: categories: Re: Functorial injective hull.
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
This is just to give different point of view to the problem.
1. Suppose we have a category C and a full subcategory H (think of H as a
subcategory of injective objects). Suppose we have a functor E:C --> H
together with natural transformation
i: Id --> E(C)
such that i is monic and ,moreover, E is weak left adjoint to the inclusion
functor H --> C. Then I claim that under two additional conditions E is
genuine adjoint and i is unit of the adjunction. The conditions are:
a. the natural transformation i is identity on H.
b. E preseves monics.
The proof is just a repetition of P.Freyd proof. We have to prove that
the extension in the diagram
i:A --> E(A)
| /
f | /
| /
I
is unique for any morphism f and "injective" I.
By applying E to this diagram and using condition a) we see that it is
sufficient to prove that E(i) is identity. Repeating Freyd's proof we see
that
E(i) is idempotent. Using condition b) we conclude that it is identity.
The conditions a) and b) are obviously satisfied in the case when E is
"injective hull functor" (of coarse a) is true up to iso, again see P,Freyd
proof).
As the unit of the adjunction is monic so the functor E reflects
epimorphisms. If in C we have that mono + epi implies iso we finally have
that i is iso and ,hence, the result of Adamek, Herrlish, Rosicky and
Tholen.
2. I would not dare to simply repeat P.Freyd argument if I don't have another
proof (in a special but important case). The proof is much more
techniqual but I believe reflects another interesting side of the problem
of functoriality
of injective resolutions.
Consider the following bicategory.
The objects are categories enriched in the closed monoidal category of
(say bounded ) chain complexes.
The 1-arrows are enriched distributors.
The 2-arrows are homotopy classes of "coherent" natural transformations (i.e.
we localize the category of natural transformations with respect to the
class of morphisms which are level quaziisomorphisms).
We have to define the composition of 1-arrows. This requires some techniques
but in a few words the result is left derived functor of the composition of
enriched distributors.
The resulting bicategory is closed on the left and right. Now, for a chain
functor
K: A --> B
we can consider the right Kan extension of it along itself in the above
bicategory (codensity monad). The Kleisli category of it is called "strong
shape theory of K" Ssh_K. It is possible to prove, that:
c). If K is a full embedding and has an enriched left adjoint then Ssh_K
is just a Kleisli category of the corresponding monad on B.
d). If B is the category of chain complexes (say bounded)in an abelian
category with enough injectives and A is full subcategory of injective
chain complexes, then homology of Ssh_K(X,Y) are isomorphic to the right
derived functor of internal Hom of B. In particular, if X and Y are
concentrated in the dimension 0 the cohomology are just the correspobding
Ext's.
Coming back to the original problem. If H\in C are abelian and satisfy the
conditions a),b) then, according to our calculations
the inclusion
K: Ch(H) ---> Ch(C)
has a right adjoint and , hence,(by point c)
Ssh_K(X,Y) = Hom(X,E(Y))
for X,Y concentrated in dimension 0. Hence by d) the injective dimension of
C is 0 and we have the result again.
Another words the injective dimension is the obstruction for nonnaturality
of the injective hull.
The same sort of theory can be developed for simplicial (or Cat) enriched
situation see
Batanin.M, Categorical Strong Shape THeory, Cahiers de Topologie et Geom,
v,XXXVIII-1(1997)p. 3-66.
I think some other results of nonaturality (as , for example, the result of
Shakhmatov mentioned by AHRT on p.8) are related to these strong shape
categories.
Michael Batanin.
From rrosebru@mta.ca Mon Mar 27 19:23:55 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id TAA08645
for categories-list; Mon, 27 Mar 2000 19:19:51 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Date: Mon, 27 Mar 2000 13:47:11 +0100 (BST)
To: categories@mta.ca
Subject: categories: PhD places at LFCS
X-Mailer: VM 6.43 under 20.4 "Emerald" XEmacs Lucid
Message-ID: <14559.22285.999090.675962@papa.dcs.ed.ac.uk>
From: Ian.Stark@ed.ac.uk
CC: Ian.Stark@ed.ac.uk
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
PhD positions available for October 2000
Laboratory for Foundations of Computer Science
Division of Informatics, University of Edinburgh
Applications are open for students to take up PhD places at
Edinburgh in October 2000. Supporting funds are available for
postgraduates of any nationality.
The Laboratory for Foundations of Computer Science is one of the
world's leading centres of research into theoretical computer
science and its application. An important part of this is its
active community of research students, currently over 20 strong.
LFCS runs a 3-year PhD programme; this includes a series of taught
courses which provide a broad background in the theory of
computation, and prepare students to do their own research work.
All students are directly supervised by an academic staff member.
The Laboratory and the Division fund some studentships of their own,
open to applicants of any nationality. UK students can also apply
for one of several grants awarded to the Division by the EPSRC.
For more information, including details of how to apply, please
consult our web site.
http://www.lfcs.informatics.ed.ac.uk/research/students.html
--------------------------------------------------------------------
Ian Stark
Deputy Director, LFCS http://www.lfcs.informatics.ed.ac.uk
From rrosebru@mta.ca Wed Mar 29 15:54:59 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id PAA10293
for categories-list; Wed, 29 Mar 2000 15:47:16 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Received: from zent.mta.ca (zent.mta.ca [138.73.101.4])
by mailserv.mta.ca (8.9.3/8.9.3) with SMTP id NAA21877
for ; Wed, 29 Mar 2000 13:34:53 -0400 (AST)
X-Received: FROM thebe.nul.ls BY zent.mta.ca ; Wed Mar 29 13:35:43 2000
X-Received: from mawanda.nul.ls ([196.24.2.251])
by thebe.nul.ls (8.8.7/8.8.7) with SMTP id TAA02762
for ; Wed, 29 Mar 2000 19:31:08 +0200
Message-Id: <3.0.1.32.20000329193641.00694528@thebe.nul.ls>
X-Sender: mmmawanda@thebe.nul.ls
X-Mailer: Windows Eudora Light Version 3.0.1 (32)
Date: Wed, 29 Mar 2000 19:36:41 +0200
To: cat-dist@mta.ca
From: "M.M. Mawanda"
Subject: categories: stupid question?
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
I have been asked the following question: Is it true that any function
defined in a real number closed interval [a,b] (there is not a hypothesis
of continuity) is bounded in an open subinterval (c,d) of [a,b]? My
spontaneous was NO. Unfortunately I cannot find a counter-example to
disapproved my answer. Can someone help.
From rrosebru@mta.ca Wed Mar 29 18:37:56 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id SAA21688
for categories-list; Wed, 29 Mar 2000 18:37:10 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 29 Mar 2000 15:23:16 -0500 (EST)
From: Peter Freyd
Message-Id: <200003292023.PAA12854@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: Re: stupid question?
Cc: mm.mawanda@nul.ls
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
M.M. Mawanda asks:
>I have been asked the following question: Is it true that any function
>defined in a real number closed interval [a,b] (there is not a hypothesis
>of continuity) is bounded in an open subinterval (c,d) of [a,b]? My
>spontaneous was NO. Unfortunately I cannot find a counter-example to
>disapproved my answer. Can someone help.
No it is not true. For example, the function defined by:
f(x) = if x is irrational then 0 else
if x = p/q where p and q are co-prime then q.
From rrosebru@mta.ca Wed Mar 29 18:42:30 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id SAA22932
for categories-list; Wed, 29 Mar 2000 18:42:12 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Jiri Adamek
Message-Id: <200003290843.KAA03913@lisa.iti.cs.tu-bs.de>
Subject: categories: bounded = accessible
To: categories@mta.ca
Date: Wed, 29 Mar 2000 10:43:24 +0200 (MET DST)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
In the community investigating coalgebras of functors F: K-> K (i.e.,
comma-categories Id/F ) the following condition in case K = Set is
quite often used:
Definition: A set functor is called bounded if there exists a cardinal
k such that for every element a of every coalgebra there exists
a subcoalgebra of cardinality less than k containing a . ("Bounded
at k " is used for the given k.)
So I wondered how this is related to accessibility, and here is the answer:
Proposition: A set functor is bounded iff it is accessible.
In fact, if k is an infinite, regular cardinal, then k-accessible =
bounded at k . For, suppose that F is bounded at k , then we
prove that in the usual category of elements of F for every object
(A,a) there exists a morhpism m: (B,b) -> (A,a) with card B < k .
It then follows easily that F is k-accessible (see e.g. 2.17 in the book
of Rosicky and myself). We can assume A nonempty, and choose x in A.
Let p:A -> FA be the coalgebra given by the constant map to a . There
exists a subcoalgebra m: (B,q) -> (A,p) for some q: B -> FB with
card B < k such that x = m(y) for an element y of B . Then b = q(y) clearly fulfills a = Fm(b), as requiered.
Conversely, suppose that F is k-accessible. Given a coalgebra
p: A -> FA , consider the collection m_i: A_i -> A of all subsets
of cardinality less than k . Since F preserves k-directed unions,
for each i there exists an i' such that m_i is contained in m_i'
and the image of p.m_i is contained in that of Fm_i' . After
iterating i -> i' -> (i')' ... k times we find a j such that
m_i is contained in m_j , and the image of p.m_j is contained in that
of Fm_j. The latter means that p can be restricted to p_j: A_j -> FA_j
forming a subcoalgebra of the coalgebra above. Since every element of
FA is contained in the image of some Fm_i , this proves that F is
bounded at k .
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
alternative e-mail address (in case reply key does not work):
J.Adamek@tu-bs.de
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
From rrosebru@mta.ca Wed Mar 29 18:44:54 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id SAA09723
for categories-list; Wed, 29 Mar 2000 18:44:48 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Received: from zent.mta.ca (zent.mta.ca [138.73.101.4])
by mailserv.mta.ca (8.9.3/8.9.3) with SMTP id SAA17342
for ; Wed, 29 Mar 2000 18:29:01 -0400 (AST)
X-Received: FROM smtpshb2.statcan.ca BY zent.mta.ca ; Wed Mar 29 18:29:52 2000
X-Received: from smtpshb2.statcan.ca (localhost [127.0.0.1])
by smtpshb2.statcan.ca (8.9.1a/8.9.1) with ESMTP id RAA23696
for ; Wed, 29 Mar 2000 17:39:03 -0500
X-Received: from smtpsha.iusd.statcan.ca (smtpsha.iusd.statcan.ca [142.205.234.131] (may be forged))
by smtpsha.iusd.statcan.ca (8.8.7/8.8.7) with ESMTP id QAA01014;
Wed, 29 Mar 2000 16:57:12 -0500
X-Received: from msxa1.statcan.ca (msxa1.statcan.ca [142.205.234.72])
by smtpsha.iusd.statcan.ca (8.8.7/8.8.7) with ESMTP id QAA00657;
Wed, 29 Mar 2000 16:56:25 -0500
X-Received: by msxa1.statcan.ca with Internet Mail Service (5.5.2448.0)
id ; Wed, 29 Mar 2000 16:48:10 -0500
Message-ID: <2C04611DA826D311A66D00902715763B0760C2@msxa4.itsd.statcan.ca>
From: "Wendt, Michael - SSMD/DMES"
To: categories@mta.ca
Subject: categories: RE: stupid question?
Date: Wed, 29 Mar 2000 16:48:16 -0500
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2448.0)
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
How about the following?
f(x) = 0 if x is irrational and
f(a/b) = a, where a/b is a fraction in lowest terms
Certainly within any open interval, there are rationals of arbitrarily large
numerator.
For a function that is not bounded above or below, how about:
f(x) = 0 if x is irrational
f(a/b) = a if b is even
f(a/b) = -a if b is odd
-----Original Message-----
From: M.M. Mawanda [mailto:mm.mawanda@nul.ls]
Sent: March 29,2000 4:08 PM
To: cat-dist@mta.ca
Subject: categories: stupid question?
I have been asked the following question: Is it true that any function
defined in a real number closed interval [a,b] (there is not a hypothesis
of continuity) is bounded in an open subinterval (c,d) of [a,b]? My
spontaneous was NO. Unfortunately I cannot find a counter-example to
disapproved my answer. Can someone help.
From rrosebru@mta.ca Wed Mar 29 19:21:46 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id TAA18092
for categories-list; Wed, 29 Mar 2000 19:20:01 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 29 Mar 2000 18:13:53 -0500 (EST)
From: maxkanov@math.upenn.edu (Max Kanovitch)
Message-Id: <200003292313.SAA14643@hans.math.upenn.edu>
To: categories@mta.ca
Subject: categories: Re: Re: stupid question?
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Dear M.M. Mawanda,
> >I have been asked the following question: Is it true that any function
> >defined in a real number closed interval [a,b] (there is not a hypothesis
> >of continuity) is bounded in an open subinterval (c,d) of [a,b]?
The real fun is about a function f such that
f is unbounded in any open interval (c,d), and
in addition to that: f(x+y) = f(x)+f(y).
> Date: Wed, 29 Mar 2000 15:23:16 -0500 (EST)
> From: Peter Freyd
> Subject: categories: Re: stupid question?
>
> M.M. Mawanda asks:
>
> >I have been asked the following question: Is it true that any function
> >defined in a real number closed interval [a,b] (there is not a hypothesis
> >of continuity) is bounded in an open subinterval (c,d) of [a,b]? My
> >spontaneous was NO. Unfortunately I cannot find a counter-example to
> >disapproved my answer. Can someone help.
>
> No it is not true. For example, the function defined by:
>
> f(x) = if x is irrational then 0 else
> if x = p/q where p and q are co-prime then q.
>
From rrosebru@mta.ca Thu Mar 30 09:10:36 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA14592
for categories-list; Thu, 30 Mar 2000 09:08:35 -0400 (AST)
X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs
Date: Wed, 29 Mar 2000 20:32:21 -0500 (EST)
From: Michael Barr
X-Sender: barr@triples.math.mcgill.ca
To: categories@mta.ca
Subject: categories: Re:stupid question?
In-Reply-To: <200003292023.PAA12854@saul.cis.upenn.edu>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
It is not even true for additive functions. Take a Hamel base and send
every element of the base to 1.
On Wed, 29 Mar 2000, Peter Freyd wrote:
> M.M. Mawanda asks:
>
> >I have been asked the following question: Is it true that any function
> >defined in a real number closed interval [a,b] (there is not a hypothesis
> >of continuity) is bounded in an open subinterval (c,d) of [a,b]? My
> >spontaneous was NO. Unfortunately I cannot find a counter-example to
> >disapproved my answer. Can someone help.
>
> No it is not true. For example, the function defined by:
>
> f(x) = if x is irrational then 0 else
> if x = p/q where p and q are co-prime then q.
>
From rrosebru@mta.ca Thu Mar 30 09:10:37 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA18327
for categories-list; Thu, 30 Mar 2000 09:09:38 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Todd Wilson
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <14562.49993.312683.542317@goedel.engr.csufresno.edu>
Date: Wed, 29 Mar 2000 19:00:25 -0800 (PST)
To: categories@mta.ca
Subject: categories: Re: stupid question?
In-Reply-To: <200003292313.SAA14643@hans.math.upenn.edu>
References: <200003292313.SAA14643@hans.math.upenn.edu>
X-Mailer: VM 6.75 under 21.1 (patch 3) "Acadia" XEmacs Lucid
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
On Wed, 29 Mar 2000, Max Kanovitch wrote:
> The real fun is about a function f such that
> f is unbounded in any open interval (c,d), and
> in addition to that: f(x+y) = f(x)+f(y).
Using AC/Zorn's Lemma, we can construct 2^(2^Aleph_0) such functions,
as follows. Let B be a basis for the reals R as a rational vector
space. Clearly, |B| = 2^Aleph_0. For any non-empty proper subset C
of B, let g be its characteristic function (g(x)=1 if x in C, g(x)=0
otherwise) and let f be the unique linear extension of g to R. Then f
is linear, and its graph is dense in R^2, since, if c and d are such
that g(c)=1 and g(d)=0, then f(qc+rd) = q for all rationals q,r, and r
can be varied to make qc+rd as close as desired to any given real.
--
Todd Wilson
Computer Science Department
California State University, Fresno
From rrosebru@mta.ca Thu Mar 30 09:13:27 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA27797
for categories-list; Thu, 30 Mar 2000 09:13:22 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 30 Mar 2000 07:57:56 -0500 (EST)
From: Peter Freyd
Message-Id: <200003301257.HAA17186@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: unbounded choice
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Max and Mike both mentioned that there are addition-preserving
self-maps on the reals that are unbounded on every non-trivial
interval. But such examples require the axiom of choice. In a
different context I happened to mention that just two months ago:
Do we need the axiom of choice? If, instead, we add the axiom of
measurability, then the counterexamples disappear: let f be a
measurable midpoint-preserving map from R to R; we can easily
specialize to the case that f0 = 0, hence f is a measurable group
endomorphism; for any real a consider the induced group
homomorphism from R/aZ to R/(fa)Z; any measurable group
character is continuous and that's enough to force f to be
continuous. (28 Jan)
The example that Michael Wendt and I described (well, almost the same
example) we didn't need choice but we did need -- as all good
toponomers know -- the law of excluded middle for the equality
predicate on the reals (in the category of spatial sheaves over a
perfect space it is the case that all real-valued maps from a closed
interval are, indeed, bounded.)
From rrosebru@mta.ca Thu Mar 30 09:14:16 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id JAA24388
for categories-list; Thu, 30 Mar 2000 09:11:10 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Jiri Adamek
Message-Id: <200003300856.KAA17187@lisa.iti.cs.tu-bs.de>
Subject: categories: Re: Functorial injective hulls
To: categories@mta.ca
Date: Thu, 30 Mar 2000 10:56:04 +0200 (MET DST)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
Bill's question concerning minimal functorial injective extensions
seems very interesting. Bill's comment was:
> But by contrast, functorial injective resolutions do exist, usually
> by some sort of double-dualisation monad. What if the "hull" or minimality
> requirement is imposed on the process qua functor instead of at each
> object? Do such functors exist ?
I have two different answers:
1. NO in case of Pos (and order-embeddings): there does not exist a minimal
pair (F,f) consisting of an endofunctor F of Pos whose values are
complete lattices and a natural transformation f: Id -> F whose
components are order-embeddings
2. YES in case of Set (and monomorphisms): the embedding Id -> Id + K,
where K is the constant functor with value 1 , is minimal.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
alternative e-mail address (in case reply key does not work):
J.Adamek@tu-bs.de
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
From rrosebru@mta.ca Fri Mar 31 12:36:24 2000 -0400
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.9.3/8.9.3) id MAA31327
for categories-list; Fri, 31 Mar 2000 12:30:58 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Fri, 31 Mar 2000 12:58:24 +0200
From: POWELL Olivier
Subject: categories: icalp2000-program and registration
To: categories@mta.ca
Message-id: <38E484D0.B921B63A@cui.unige.ch>
MIME-version: 1.0
X-Mailer: Mozilla 4.72 [en] (X11; I; SunOS 5.6 sun4u)
Content-type: multipart/mixed; boundary="Boundary_(ID_JG9/5NLGvE5XRy47qWAy+w)"
X-Accept-Language: en
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
ICALP' 2000 Program, Registration and Practical Information
Sunday July 9th
Registration Opens Late Afternoon
-------------------------------------------------------------------=
-----
Monday, July 10th
9:00 - 10:00
INVITED TALK
Game Semantics: Achievements and Prospects
Samson Abramsky
10:00 - 10:50
SESSION 1
Clique is hard to approximate within n*(1-o(1))
Lars Engebretsen, Jonas Holmerin
Approximating the independence number and the chromatic
number in expected polynomial time
Michael Krivelevich, Van Vu
-------------------------------------------------------------------=
-----
10:00 - 10:50
SESSION 2
Closed Types as a Simple Approach to Safe Imperative
Multi-Stage Program
Cristiano Calcagno, Eugenio Moggi, Walid Taha
A Statically Allocated Parallel Functional Language
Alan Mycroft, Richard Sharpu
-------------------------------------------------------------------=
-----
(Coffee Break 10:50 - 11:10)
-------------------------------------------------------------------=
-----
11:10 - 12:25
SESSION 1
An Optimal Minimum Spanning Tree Algorithm
Seth Pettie, Vijaya Ramachandran
Improved shortest paths on the word RAM
Torben Hagerup
Improved algorithms for finding level ancestors in
dynamic trees
Stephen Alstrup, Jacob Holm
-------------------------------------------------------------------=
-----
11:10 - 12:25
SESSION 2
Lax Logical Relations
Gordon Plotkin, John Power, Donald Sannella, Robert
Tennent
Reasoning about Idealized Algol Using Regular Languages
Dan R. Ghica, Guy McCusker
The measurement process in domain theory
Keye Martin
-------------------------------------------------------------------=
-----
(Lunch 12:30 - 14:30)
-------------------------------------------------------------------=
-----
14:30 - 15:30
INVITED TALK
Graph Transformation as Unifying Formal Framework for
System Modeling and Model Evolution
Gregor Engels
15:30 - 16:20
SESSION 1
Monotone Proofs of the Pigeon Hole Principle
Albert Atserias, Nicola Galesi, Ricard Gavalda
Homogenization and the Polynomial Calculus
Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo,
Toniann Pitassi
-------------------------------------------------------------------=
-----
15:30 - 16:20
SESSION 2
Fully-abstract Statecharts Semantics via Intuitionistic
Kripke Structures
Gerald L=FCttgen, Michael Mendler
Algebraic Models for Contextual Nets
Roberto Bruni, Vladimiro Sassone
-------------------------------------------------------------------=
-----
(Coffee Break 16:20 - 16:40)
-------------------------------------------------------------------=
-----
16:40 - 17:30
SESSION 1
Asymptotically optimal bounds for OBDDs and the solution
of some basic OBDD problems
Beate Bollig, Ingo Wegener
Measures of Nondeterminism in Finite Automata
Juraj Hromkovic, Juhani Karhum=E4ki, Hartmut Klauck, Georg
Schnitger, Sebastian Seibert
-------------------------------------------------------------------=
-----
16:40 - 17:30
SESSION 2
LTL is expressively complete for Mazurkiewicz traces
Volker Diekert, Paul Gastin
An automata-theoretic completeness proof for Interval
Temporal Logic
B. C. Moszkowski
-------------------------------------------------------------------=
-----
(Welcome reception 18:00)
-------------------------------------------------------------------=
-----
Tuesday, July 11th
9:00 - 10:00
INVITED TALK
Which NP-hard optimization problems admit
non-trivial efficient approximation algorithms?
Johan Haastad
10:00 - 10:50
SESSION 1
Deterministic algorithms for k-SAT based on
covering codes and local search
Evgeny Dantsin, Andreas Goerdt, Edward A.
Hirsch, Uwe Sch=F6ning
Closest Vectors, Successive Minima and Dual
HKZ-Bases of Lattices
Johannes Bl=F6mer
----------------------------------------------------------------=
----
10:00 - 10:50
SESSION 2
Variable Independence, Quantifier Elimination,
and Constraint Representations
Leonid Libkin
Constraint Satisfaction Problems and Finite
Algebras
Andrei Bulatov, Andrei Krokhin, Peter Jeavons
----------------------------------------------------------------=
----
(Coffee Break 10:50 - 11:10)
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 1
An optimal online algorithm for bounded space
variable-sized bin packing
Steven S. Seiden
Resource augmentation for online bounded
space bin packing
J=E1nos Csirik, Gerhard Woeginger
Optimal projective algorithms for the list
update problem
Christoph Amb=FChl, Bernd G=E4rtner, Bernhard von
Stengel
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 2
Efficient Verification Algorithms for
One-Counter Processes
Antonin Kucera
On the Complexity of Bisimulation Problems for
Basic Parallel Processes
Richard Mayr
Decidable first-order transition logics for
PA-processes
D. Lugiez, Ph. Schnoebelen
----------------------------------------------------------------=
----
(Lunch 12:30 - 14:30)
----------------------------------------------------------------=
----
14:30 - 15:30
INVITED TALK
Non Interference for Analysis of Cryptographic
Protocols
Roberto Gorrieri
15:30 - 16:20
SESSION 1
Average bit-complexity of Euclidean algorithms
Ali Akhavi, Brigitte Vall=E9e
Planar maps and Airy phenomena
Cyril Banderier, Philippe Flajolet, Gilles
Schaeffer, Mich=E8le Soria
----------------------------------------------------------------=
----
15:30 - 16:20
SESSION 2
Analysing Input Output Capabilities of Mobile
Processes with a Generic Type System
Barbara K=F6nig
Information Flow vs. Resource Access in the
Information Asynchronous Pi-Calculus
Matthew Hennessy, James Riely
----------------------------------------------------------------=
----
(Coffee Break 16:20 - 16:40)
----------------------------------------------------------------=
----
16:40 - 17:40
AWARD TALK
Past, Present and Future of TCS
Richard Karp
----------------------------------------------------------------=
----
17:40
EATCS General Assembly
(Wine and cheese )
----------------------------------------------------------------=
----
Wednesday, July 12th
9:00 - 10:00
INVITED TALK
Alteration Verification Diagrams
Zohar Manna
10:00 - 10:50
SESSION 1
Necessary and sufficient assumptions for non
interactive zero knowledge proofs of knowledge
for all NP relations
Alfredo De Santis, Giovanni Di Crescenzo,
Giuseppe Persiano
Computational PCP: Short one-round proofs for
NP
W. Aiello, S. Bhatt, R. Ostrovsky, S.
Rajagopalan
----------------------------------------------------------------=
----
10:00 - 10:50
SESSION 2
A New Unfolding Approach to LTL Model Checking
Javier Esparza, Keijo Heljanko
Reasoning about message passing in finite state
environments
B. Meenakshi, R. Ramanujam
----------------------------------------------------------------=
----
(Coffee Break 10:50 - 11:10)
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 1
Extended notions of security for multicast
public key cryptosystems
Olivier Baudron, David Pointcheval, Jacques
Stern
One-round secure computation and secure
autonomous mobile agents
Christian Cachin, Jan Camenisch, Joe Kilian,
Joy M=FCller
Round-optimal and abuse free multi-party
contract signing
Birgit Baum-Waidner, Michael Waidner
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 2
On the centralizer of a finite set
Juhani Karhum=E4ki, Ion Petre
On the power of tree-walking automata
Frank Neven, Thomas Schwentick
Determinization of transducers over infinite
words
Marie-Pierre B=E9al, Olivier Carton
----------------------------------------------------------------=
----
(Lunch 12:30 - 14:30)
----------------------------------------------------------------=
----
(City Tours and Excursion 14:30)
----------------------------------------------------------------=
----
Thursday, July 13th
9:00 - 10:00
INVITED TALK
Graph Algorithms and Constraint Programming
Kurt Mehlhorn
10:00 - 10:50
SESSION 1
Scalable secure storage when half the system is
faulty
Noga Alon, Haim Kaplan, Michael Krivelevich,
Dahlia Malkhi, Julien Stern
Dual-bounded hypergraphs: Generating partial
and multiple transversals
Endre Boros, Vladimir Gurvich, Leonid
Khachiyan, Kazuhisa Makino
----------------------------------------------------------------=
----
10:00 - 10:50
SESSION 2
Revisiting the correspondence between cut
elimination and normalisation
Jos=E9 Espirito Santo
Negation Elimination from Simple Equational
Formulae
Reinhard Pichler
----------------------------------------------------------------=
----
(Coffee Break 10:50 - 11:10)
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 1
Hardness of set cover with intersection 1
V.S. Anil Kumar, Sunil Arya, H. Ramesh
Strong inapproximability of the basic k-Spanner
Problem
Michael Elkin, David Peleg
Approximating Minimum Spanning Sets in
Hypergraphs and Polymatroids
Gregor Baudis, Clemens Gr=F6pl, Stefan Hougardy,
Till Nierhoff, Hans J=FCrgen Pr=F6mel
----------------------------------------------------------------=
----
11:10 - 12:25
SESSION 2
Infinite series parallel posets: logic and
languages
Dietrich Kuske
On deciding if deterministic Rabin language is
in Buchi class
Tomasz Fryderyk Urbanski
On Message Sequence Graphs and Finitely
Generated Regular MSC Languages
Jesper G. Henriksen, Madhavan Mukund, K.
Narayan Kumar, P.S. Thiagarajan
----------------------------------------------------------------=
----
(Lunch 12:30 - 14:30)
----------------------------------------------------------------=
----
14:30 - 15:30
INVITED TALK
Pseudorandomness
Oded Goldreich
15:30 - 16:20
SESSION 1
A bound on the capacity of backoff and
acknowledgement based protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath
Kannan, Mike Paterson
Deterministic radio broadcasting
Bogdan Chlebus, Leszek Gasieniec, Anna =D6stlin,
John Michael Robson
----------------------------------------------------------------=
----
15:30 - 16:20
SESSION 2
A Finite w-complete Equational Specification of
Interleaving
Wan Fokkink, Bas Luttik
A Complete Axiomatization for Observational
Congruence of Prioritized Finite-State
Behaviors
Mario Bravetti, Roberto Gorrieri
----------------------------------------------------------------=
----
(Coffee Break 16:20 - 16:40)
----------------------------------------------------------------=
----
16:40 - 17:30
SESSION 1
Tight size bounds for packet headers in narrow
meshes
Micah Adler, Faith Fich, Leslie Ann Goldberg,
Mike Paterson
Wavelength assignment problem on all-optical
networks with k fibres per link
Luciano Margara, Janos Simon
----------------------------------------------------------------=
----
16:40 - 17:30
SESSION 2
On the logical characterisation of
performability properties
Christel Baier, Boudewijn Haverkort, Holger
Hermanns, Joost-Pieter Katoen
On the Representation of Timed Polyhedra
Olivier Bournez, Oded Maler
----------------------------------------------------------------=
----
(Conference dinner 20:00)
----------------------------------------------------------------=
----
-------------------------------------------------------------------=
-----
Friday July 14th
9:00 - 10:00
INVITED TALK
Min-wise Independent Permutations: Theory and Practice
Andrei Broder
10:00 - 10:50
SESSION 1
Testing acyclicity of directed graphs in sublinear time
Michael Bender, Dana Ron
Computing the girth of a planar graph
Hristo N. Djidjev
-------------------------------------------------------------------=
-----
10:00 - 10:50
SESSION 2
Lower bounds are not easier over the reals: inside PH
Herv=E9 Fournier, Pascal Koiran
Unlearning helps
Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan
-------------------------------------------------------------------=
-----
(Coffee Break 10:50 - 11:10)
-------------------------------------------------------------------=
-----
11:10 - 12:25
SESSION 1
Fast approximation schemes for Euclidean
multiconnectivity problems
Artur Czumaj, Andrzej Lingas
Approximate TSP in graphs with forbidden minors
Michelangelo Grigni
Polynomial time approximation schemes for general
multiprocessor job shop scheduling
Klaus Jansen and Lorant Porkolab
-------------------------------------------------------------------=
-----
11:10 - 12:25
SESSION 2
The many faces of a translation
Pierre McKenzie, Thomas Schwentick, Denis Th=E9rien,
Heribert Vollmer
Gales and the constructive dimension of individual
sequences
Jack Lutz
The global power of additional queries to p-random
oracles
Wolfgang Merkle
-------------------------------------------------------------------=
-----
(Lunch 12:30 - 14:30)
-------------------------------------------------------------------=
-----
WORKSHOPS START AT 14:30
(* See individual workshop programs for schedule details.)
-------------------------------------------------------------------=
-----
Registration
You may register electronically (opens in the begining of april) at t=
he
ICALP home page. The online registration application accepts MasterCa=
rd,
Visa and American Express cards. If you do not have one of these cred=
it
cards, or if you prefer not to register online, please download the
registration form.
Registration Fees
Includes entrance to all sessions and workshops, a copy of the procee=
dings,
a copy of the workshops proceedings, luncheon, coffee breaks, social =
events
and the EATCS membership for one year. (1US=3D1.67CHF at the moment o=
f the
print)
CHF 550.00 EATCS members registration received before June 1, 2000
CHF 650.00 Non EATCS members registration received before June 1, 2=
000
CHF 400.00 Student registration received before June 1, 2000
CHF 650.00 EATCS members registration after June 1, 2000
CHF 750.00 Non EATCS members registration after June 1, 2000
CHF 500.00 Student registration after June 1, 2000
CHF 150.00 Workshops only registration received before June 1, 2000
CHF 200.00 Workshops only registration after June 1, 2000
Practical Information
-------------------------------------------------------------------=
-----
-------------------------------------------------------------------=
-----
Conference Site
Universit=E9 de Gen=E8ve - UNI BASTIONS
3, place de l'Universit=E9 (at Rue de Candolle)
Geneva
How to get to Geneva
Swissair and Crossair have been appointed official carrier for ICALP =
'2000.
To book the special conference fare, please contact your nearest Swis=
sair
office or, in the US and UK, the appointed travel agent listed below.=
To
obtain a discount fare, give the ticket agent the code SR IDS page GC=
GRF
C00-C26 and refer to the event as the 27th International Colloquium o=
n
Automata, Languages and Programming.
The official Swissair designated airline ticketing agency is
North American Participants:
Conferences International, Inc.
Toll Free in US and Canada
1-800-221-8747
Fax: 1-508-872-5566
United Kingdom Participants:
Karen Hammond
Tel 44-171-499-7611
Fax 44-171-493-0326
Participants from other countries should contact their nearest Swissa=
ir
office. If other arrangements including ground and rail are required,
contact your travel agent for assistance.
Accommodations
In 2000, ICALP will be held in the old campus of the University of Ge=
neva.
The hotels listed below have reserved a block of rooms at special ICA=
LP
rates. The discounted rates offered by the Hotel du Midi, a very pres=
tigious
4 star establishment, are an especially good value.
Prices for the hotels are guaranteed but due to the high demand of ro=
oms
during the month of July in Geneva, register as early as possible to =
assure
your choice. The hotels are within 5-15 minutes walking distance from=
the
University of Geneva campus.
To reserve accommodations, contact the selected hotel, preferably, by=
fax
and furnish the following information:
Name - Affiliation - Address
Phone and Fax
Accommodations requested (Single/Double)
Number in party (Ages of children)
Arrival and Departure Date/Time
Credit Card Guarantee (Most are accepted)
Please cite: Special rate for the University of Geneva - ICALP 20=
00
NOGA HILTON GENEVE *****
CONTACT Mme Valerie Bonvin
TEL +41 22 908-9193
FAX +41 22 908-9091
SINGLE CHF 330
DOUBLE CHF 380
HOTEL DU MIDI ****
CONTACT Mme S. Ianna
TEL +41 22 731-7800
FAX +41 22 731-0020
SINGLE CHF 140
DOUBLE CHF 180
HOTEL LE GRENIL ***
CONTACT Mme Christine Hager
TEL +41 22 328-3055
FAX +41 22 321-6010
SINGLE CHF 95 (breakfast included)
DOUBLE CHF 130 (breakfast included)
Other Accommodations
For information and reservation of other accommodations and tour pack=
ages,
you or your travel agent may contact the Geneva Tourist Office. You c=
an fax
your data as above, any other relevant information and ask for a room
reservation. Fax +41 22 909-7021 or call +41 22 909-7020 or write PO =
Box
1602, CH-1211 Geneva 1, Switzerland. Also, take a look at their site =
at
http://www.geneve-tourisme.ch
Alternatively, a limited number of very inexpensive rooms are availab=
le at
the Student Housing (Cit=E9 Universitaire). If you are interested in =
such
accomodations please contact icalp@cui.unige.ch
Local Transportation
>From the airport:
A taxi from the airport to either hotels or University will cost abou=
t CHF
30. Alternatively you may take the train from the airport to the main=
train
station - a 5 minute walk from the first two hotels. The ride will co=
st
around CHF 5 and will take 10 minutes. Purchase a ticket before board=
ing the
train.
>From hotels to the University:
It is a 10 minute walk from the first two hotels. You may cross the r=
iver
via either the Pont des Bergues or Pont de la Machine and then take R=
ue de
la Corraterie to Place Neuve. From the other hotel is a very short wa=
lk, see
the enclosed map. The University is located at the park called Promen=
ade des
Bastions.
By public transportation, take tramway number 13 from the main train =
station
to the fourth stop (called Plainpalais). From there walk by rue du Co=
nseil
G=E8n=E8ral until you reach the Promenade des Bastions.
Note: When using any local transportation, you need to purchase a tic=
ket in
advance at the machine located at the bus stop; the cost is CHF 2.20.=
This
ticket is valid for one hour and you may take as many connections as =
you
want. Also note that the machine does not give change, and if you ent=
er a
bus without a valid transportation ticket you risk being required to =
pay a
fine of about CHF 100 and a visit to the police station.
Cuisine
At ICALP '2000, luncheon will be served on the University campus to a=
ll
registrants on all five days and refreshments will be available durin=
g
breaks. On Thursday evening, there will be the official banquet of th=
e
conference. Please be sure to indicate on your registration form whet=
her you
prefer vegetarian meals.
At other times, participants will have a broad choice of dining optio=
ns
offering international and gourmet fare all within walking distance o=
f
accommodations and many along the shores of Lake Geneva. The traditio=
nal and
most popular dishes among the local population are cheese fondue and
raclette, delicious local wines, and lake perch.
Currency and Credit Cards
The unit of currency is the Swiss franc (CHF). Notes are issued in
denominations of 10, 20, 50, 100, 200, and 1,000. Coins are issued in
denominations of 5, 10, and 20 centimes, and .5, 1, 2, and 5 Swiss fr=
ancs.
At the moment of the print, 1US was worth CHF 1.67, but since this ra=
te
changes very often, check the real rate at the necessary moment. Most
hotels, large stores, restaurants, and petrol stations accept all maj=
or
credit cards (American Express, MasterCard, Visa, Diners Club, Euroca=
rd).
Location
Geneva is situated along the banks of Lac L=E9man (Lake Geneva) and L=
e Rh=F4ne.
The lake showcases the plumed fountain Jet d'Eau, and various distric=
ts of
Geneva are connected by bridges across the waterways. The University =
of
Geneva where ICALP '2000 will convene is located on the `Left Bank' o=
ff
Place Neuve and along the Promenade des Bastions near the Old Town se=
ction
of Geneva.
The two first ICALP designated hotels (Noga and du Midi) are located
lakeside - on the `Right Bank' - and are within walking distance of t=
he
University campus. It is a 10-15 minute walk which crosses through `O=
ld
Town'. Also, there is regular bus service running to the University, =
so
ICALP participants may come and go throughout the day. The Hotel Le G=
renil
and the University are both situated on the `Left Bank' and are very =
close.
Geneva is a city of water parks and gardens and welcoming walkways wh=
ich
encourage exploration of the historical sites, museums, and internati=
onal
business and shopping districts. The University of Geneva is located =
near
`Old Town' an area dotted with sidewalk cafes, student life, and buil=
ding
antiquities dating back to the 5th century.
Geneva is a crossroads situated in the heart of Europe and linked to =
the
world by a vast network of motorways, airlines and railways. For thos=
e
planning to attend ICALP'2000 in Geneva, it is an excellent opportuni=
ty to
organize short trips into the countryside of charming villages and
vineyards. Tours to please all ages and interests are available inclu=
ding
afternoon train excursions, shopping cruises on Lake Geneva and The R=
hone,
and bus and cablecar trips in the Alps.
For some, the most inviting attraction will be mountain climbing. The=
high
mountains are situated less than half an hour drive from Geneva. In e=
arly
July, a very popular and almost mandatory activity is swimming in the=
lake
Geneva, so serious and not so serious swimmers should plan accordingl=
y!
Climate
The climate in early July should be warm but still very pleasant with=
nice
evenings and breezes off the Lake. There may be showers but we can al=
so
expect sunny days.
Passports and Visas
A valid passport is required for entry into Switzerland. Some nationa=
ls may
also require a visa for Switzerland, and if you plan to visit France =
one may
be required there. Please check with your travel agent or consulate t=
o
determine whether a visa will be required.