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.