September 1998 - Categories - categories.org.au

Abstract Algebraic Geometry
by Zhaohua Luo 28 Sep '98

28 Sep '98

The following short note (see the abstract below) A Note on Reduced Categories is available on Categorical Geometry Homepage at the following address: http://www.azd.com/reduced.html Note that this file (together with most of the other files in the homepage) can be read now by any viewer capable of graphics (the symbols are included as gif. files). Z. Luo __________________________________________________________________ A Note on Reduced Categories Zhaohua Luo Abstract: In this note we introduce the notion of a reduced object for any category A with a strict initial object 0. A pair of parallel maps f, g: X --> Z is called "disjointed" if its kernel is the initial map to X. It is called "nilpotent" if any map t: T --> X such that (tf, tg) is disjointed is initial. An object X is called "reduced" if any pair of distinct parallel maps with domain X is not nilpotent. A category A is called "reduced" if any object is reduced. One can show that any epic quotient of a reduced object is reduced. A class D of objects of A is called "uni-dense" if any non-initial object is the codomain of a map with a non-initial object in D as domain. We show that any uni-dense class D of a reduced category A is a set of generators. Other properties and criterions of reduced categories are also studied. --------------A7DB306CE63DF22C54674FBE Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit <HTML> <BODY TEXT="#000000" BGCOLOR="#FFFFEA" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000"> The following short note (see the abstract below) A Note on Reduced Categories is available on Categorical Geometry Homepage at the following address: <A HREF="http://www.azd.com/reduced.html">http://www.azd.com/reduced.html</A> Note that this file (together with most of the other files in the homepage) can be read now by any viewer capable of graphics (the symbols are included as gif. files). Z. Luo __________________________________________________________________ A Note on Reduced Categories Zhaohua Luo Abstract: In this note we introduce the notion of a reduced object for any category A with a strict initial object 0. A pair of parallel maps f, g: X --> Z is called "disjointed" if its kernel is the initial map to X. It is called "nilpotent" if any map t: T --> X such that (tf,  tg) is disjointed is initial. An object X is called "reduced" if any pair of distinct parallel maps with domain X is not nilpotent. A category A is called "reduced" if any object is reduced. One can show that any epic quotient of a reduced object is reduced. A class D of objects of A is called "uni-dense" if any non-initial object is the codomain of a map with a non-initial object in D as domain. We show that any uni-dense class D of a reduced category A is a set of generators. Other properties and criterions of reduced categories are also studied.           </BODY> </HTML> --------------A7DB306CE63DF22C54674FBE--

1 0

CSL'99 2nd CFP *deadlines modified* (Text & LaTex versions)
by Eva Ullan 26 Sep '98

26 Sep '98

____________________________________________________ My apologies if you receive this more than once! ____________________________________________________ =================================== 2nd CALL FOR PAPERS -- CSL'99 Annual Conference of the European Association for Computer Science Logic September 20-25, 1999, Madrid, Spain =================================== __________________________________________________ IMPORTANT REMARK The proceedings volume will be available at the conference. In order to enable this, the DEADLINES for paper submission and notification of acceptance have been slightly MODIFIED w.r.t. the announcement made in the 1st call for papers. __________________________________________________ CSL is the annual conference of the European Association for Computer Science Logic (EACSL). The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science. Suggested, but not exclusive, topics of interest include: * abstract datatypes, * automated deduction, * categorical and topological approaches, * concurrency theory, * constructive mathematics, * database theory, * domain theory, * finite model theory, * lambda and combinatory calculi, * logical aspects of computational complexity, * logical foundations of programming paradigms, * linear logic, * modal and temporal logics, * model checking, * program logics and semantics, * program specification, transformation and verification, * rewriting, * symbolic computation. EACSL BOARD Marc Bezem (Utrecht, President) Ian Stewart (Leicester, Vice-President) Clemens Lautemann (Mainz, Treasurer) Peter Hajek (Prague) Simone Martini (Udine) Christine Paulin (Paris) Moshe Vardi (Houston) Johann Makowsky (Haifa) Alexander Razborov (Moscow) EACSL homepage: http://www.dimi.uniud.it/~eacsl PROGRAM COMMITEE Samson Abramsky (Edinburgh, UK) Marc Bezem (Utrecht, The Netherlands) Peter Clote (Munich, Germany) Hubert Comon (Cachan, France) Jorg Flum (Freiburg i.Br., Germany) (co-chair) Harald Ganzinger (Saarbrucken, Germany) Neil Immerman (Amherst, USA) Neil Jones (Copenhagen, Denmark) Jan Maluszynski (Linkoping, Sweden) Michael Maher (Brisbane, Australia) Catuscia Palamidessi (Pennsylvania, USA) Mario Rodriguez-Artalejo (Madrid, Spain) (co-chair) Wolfgang Thomas (Aachen, Germany) Jerzy Tiuryn (Warsaw, Poland) Glynn Winskel (Aarhus, Denmark) Martin Wirsing (Munich, Germany) LOCAL ORGANIZING COMMITTEE J. Carlos Gonzalez-Moreno Teresa Hortala-Gonzalez Javier Leach-Albert (chair) Paco Lopez-Fraguas Fernando Saenz-Perez Eva Ullan-Hernandez SCIENTIFIC PROGRAMME In addition to invited lectures and contributed papers, there will be two tutorials on theorem proving and rewriting techniques, scheduled on September 24 afternoon (Friday) and September 25 morning (Saturday), immediately after the main conference. ** September 20--24, 1999: Invited Lectures and Contributed Papers The list of invited speakers will include: Jose Luis Balcazar (Barcelona, Spain) Javier Esparza (Munich, Germany) Martin Grohe (Freiburg, Germany) Peter D. Mosses (Aarhus, Denmark) V. Vianu (San Diego, USA) ** September 24--25, 1999: CSL Tutorials Douglas Howe (Bell Labs, USA) Aart Middeldorp (Tsukuba, Japan) PAPER SUBMISSIONS Submitted papers must be written in English and describe work not previously published. They must not be submitted concurrently to a journal or to another conference. Papers authored or coauthored by members of the Program Committee are not allowed. Submissions must not exceed 15 pages, including title page, figures, and references. The title page must contain: title and authors; physical and e-mail addresses; telephone and (if available) fax number for each author; identification of corresponding author, if not the first author; an abstract of no more than 200 words; a list of keywords. Submissions must arrive by March 19, 1999, and notifications of acceptance will be sent by May 31, 1999. Authors are invited to send manuscripts by electronic mail, as uuencoded gzipped postcript files: * see the conference home page for instructions http://mozart.sip.ucm.es:1580/csl99 * or send an empty message with subject "submission information'' to csl99org(a)eucmos.sim.ucm.es Those authors without access to the facilities for electronic submission can alternatively submit five hardcopies to: Prof. Mario Rodriguez Artalejo, CSL'99 Departamento de Sistemas Informaticos y Programacion Facultad de Matematicas, Universidad Complutense de Madrid Av. Complutense s/n E-28040 Madrid Spain E-mail: mario(a)sip.ucm.es Phone: +34 1 3 94 45 12 Fax: +34 1 3 94 46 07 PUBLICATION Papers accepted by the Program Committee must be presented at the conference and will appear in a proceedings volume, to be published by Springer Verlag in the "Lecture Notes in Computer Science" series. The second refereeing round which was requested in previous CSL editions before accepting a paper for publication in the proceedings, has been suppressed following the decision taken by the EACSL membership meeting held during CSL'98 (Brno, Czech Republic, August 25th 1998). Final versions of accepted papers will be due by July 12, 1999. The format for camera-ready manuscripts will be that of Springer LNCS; instructions can be found in the LNCS home page at: http://www.springer.de/comp/lncs/index.html IMPORTANT DATES Paper submissions March 19, 1999 Notifications of acceptance May 31, 1999 Final version due: July 12, 1999 CSL'99 main conference September 20-24, 1999 CSL'99 Tutorials September 24-25, 1999 ADDITIONAL INFORMATION CSL'99 home page: http://mozart.sip.ucm.es:1580/csl99 CSL'99 local organization: csl99org(a)eucmos.sim.ucm.es %%%%%%%%%%%%%%%%%%%%%% LATEX VERSION %%%%%%%%%%%%%% % 2nd Call for Papers, CSL'99. % Last revision: September 24, 1998. \documentstyle{article} \oddsidemargin 6pt \evensidemargin 6pt \marginparwidth 90pt \marginparsep 10pt \topmargin -30pt \headheight 12pt \headsep 25pt \footheight 12pt \footskip 30pt \columnsep 10.5pt \columnseprule 0pt \addtolength{\oddsidemargin}{-2.3cm} \setlength{\textwidth}{20cm} %{18.7cm} \addtolength{\topmargin}{-1cm} \setlength{\textheight}{27cm} \pagestyle{empty} \begin{document} % Heading \begin{center} {\large \bf 2nd CALL FOR PAPERS -- CSL'99} \end{center} \begin{center} {\Large \bf Annual Conference of the }\\[1.5ex] {\Large \bf European Association for Computer Science Logic} \end{center} \begin{center} {\large \bf Madrid, Spain, September 20-25, 1999} \end{center} \vspace*{0.15in} % Left column \parbox[t]{6.5cm}{%6.3cm \footnotesize \noindent {\bf Program Committee:} \vspace*{0.05in} \begin{tabular}{l} Samson Abramsky (Edinburgh, UK)\\ Marc Bezem (Utrecht, The Netherlands)\\ Peter Clote (Munich, Germany)\\ Hubert Comon (Cachan, France)\\ J\"{o}rg Flum (Freiburg i.Br., Germany) \\ \hspace{1cm} ({\bf co-chair})\\ Harald Ganzinger (Saarbr\"{u}cken, Germany)\\ Neil Immerman (Amherst, USA)\\ Neil Jones (Copenhagen, Denmark)\\ Jan Maluszynski (Link\"{o}ping, Sweden)\\ Michael Maher (Brisbane, Australia)\\ Catuscia Palamidessi (Pennsylvania, USA)\\ Mario Rodr\'{\i}guez-Artalejo (Madrid, Spain) \\ \hspace{1cm} ({\bf co-chair})\\ Wolfgang Thomas (Aachen, Germany)\\ Jerzy Tiuryn (Warsaw, Poland)\\ Glynn Winskel (Aarhus, Denmark)\\ Martin Wirsing (Munich, Germany)\\ \end{tabular} \vspace*{0.10in} \noindent {\bf Invited Speakers:} \vspace*{0.05in} \begin{tabular}{l} Jos\'{e} Luis Balc\'{a}zar (Barcelona, Spain)\\ Javier Esparza (Munich, Germany)\\ Martin Grohe (Freiburg, Germany)\\ Peter D. Mosses (Aarhus, Denmark)\\ V. Vianu (San Diego, USA) \end{tabular} \vspace*{0.10in} \noindent {\bf Tutorialists:} \vspace*{0.05in} \begin{tabular}{l} Douglas Howe (Bell Labs, USA)\\ Aart Middeldorp (Tsukuba, Japan) \end{tabular} \vspace*{0.10in} \noindent {\bf Local Organizing Committee:} \vspace*{0.05in} \begin{tabular}{l} J. Carlos Gonz\'{a}lez-Moreno\\ Teresa Hortal\'{a}-Gonz\'{a}lez\\ Javier Leach-Albert ({\bf chair})\\ Paco L\'{o}pez-Fraguas\\ Fernando S\'{a}enz-P\'{e}rez\\ Eva Ull\'{a}n-Hern\'{a}ndez \end{tabular} \vspace*{0.10in} \noindent {\bf EACSL Board:} \vspace*{0.05in} \begin{tabular}{l} Marc Bezem (Utrecht, President)\\ Iain Stewart (Leicester, Vice-President)\\ Clemens Lautemann (Mainz, Treasurer)\\ Peter Hajek (Prague)\\ Simone Martini (Udine)\\ Christine Paulin (Paris)\\ Moshe Vardi (Houston)\\ Johann Makowsky (Haifa)\\ Alexander Razborov (Moscow)\\ \end{tabular} \vspace*{0.15in} \noindent {\bf EACSL homepage:} \vspace*{0.05in} \begin{tabular}{l} http://www.dimi.uniud.it/\~{}eacsl \end{tabular} \vspace*{0.15in} \noindent {\bf Important Dates:} \vspace*{0.05in} \begin{tabular}{l} Paper submissions: \\ ~~~~ March 19, 1999 \\ Notifications of acceptance: \\ ~~~~ May 31, 1999 \\ Final version due: \\ ~~~~ July 12, 1999 \\ CSL'99 main conference: \\ ~~~~ September 20-24, 1999 \\ CSL'99 Tutorials: \\ ~~~~ September 24-25, 1999 \end{tabular} } % \end{parbox} % Right column. No blank line here! \parbox[t]{5mm}{ \rule[-22.0cm]{0.2mm}{22.5cm} } %\end{parbox} \begin{minipage}[t]{11.0cm}%{11.5cm} \small {\bf Aims and Scope of the Conference:} {\bf CSL} is the annual conference of the {\em European Association for Computer Science Logic} (EACSL). The conference is intended for computer scientistswhose research activities involve logic, as well as for logicians working on issues significant for computer science. Suggested, but not exclusive, topics of interest include: abstract datatypes, automated deduction, categorical and topological approaches, concurrency theory, constructive mathematics, database theory, domain theory, finite model theory, lambda and combinatory calculi, logical aspects of computational complexity, logical foundations of programming paradigms, linear logic, modal and temporal logics, model checking, program logics and semantics, program specification, transformation and verification, rewriting, symbolic computation. \vspace*{0.12in} \noindent {\bf Scientific Programme:} In addition to invited lectures and contributed papers, there will be two tutorials on theorem proving and rewriting techniques, scheduled on September 24 afternoon (Friday) and September 25 morning (Saturday), immediately after the main conference. \vspace*{0.12in} \noindent {\bf Paper Submissions:} Submitted papers must be written in English and describe work not previously published. They must not be submitted concurrently to a journal or to another conference. Papers authored or co-authored by members of the Program Committee are not allowed. Submissions must not exceed 15 pages, including title page, figures, and references. The title page must contain: title and authors; physical and e-mail addresses; telephone and (if available) fax number for each author; identification of corresponding author, if not the first author; an abstract of no more than 200 words; a list of keywords. Submissions must arrive by {\bf March 19, 1999}, and notifications of acceptance will be sent by {\bf May 31, 1999}. Authors are invited to send manuscripts by electronic mail, as uuencoded gzipped postcript files (see the conference home page for instructions, or send an empty message with subject ``submission information'' to csl99org(a)eucmos.sim.ucm.es) Those authors without access to the facilities for electronic submission can alternatively submit {\em five hardcopies} to: \vspace*{0.05in} \begin{tabular}{l} Prof. Mario Rodr\'{\i}guez-Artalejo, CSL'99 \\ Departamento de Sistemas Inform\'{a}ticos y Programaci\'{o}n \\ Facultad de Matem\'{a}ticas, Universidad Complutense de Madrid \\ Av. Complutense s/n ~~~~~~~~~~ Phone: +34 1 3 94 45 12 \\ E-28040 Madrid ~~~~~~~~~~~~~~~~~ Fax: +34 1 3 94 46 07 \\ Spain ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ E-mail: mario(a)sip.ucm.es \end{tabular} \vspace*{0.12in} \noindent {\bf Publication:} Papers accepted by the Program Committee must be presented at the conference and {\bf will appear in a proceedings volume}, to be published by Springer Verlag in the ``Lecture Notes in Computer Science'' series. The second refereeing round which was requested in previous CSL editions before accepting a paper for publication in the proceedings, has been suppressed following the decision taken by the EACSL membership meeting held during CSL'98 (Brno, Czech Republic, August 25th 1998). Final versions of accepted papers will be due by {\bf July 12, 1999}. The format for camera-ready manuscripts will be that of Springer LNCS; instructions can be found in the LNCS home page at http://www.springer.de/comp/lncs/index.html. \vspace*{0.12in} \noindent {\bf Important Remark:} The proceedings volume will be available at the conference. In order to enable this, the deadlines for paper submission and notification of acceptance have been slightly modified w.r.t. the announcement made in the 1st call for papers. \vspace*{0.15in} \noindent {\bf Additional Information:} \vspace*{0.05in} \begin{tabular}{ll} CSL'99 home page: & http://mozart.sip.ucm.es:1580/csl99 \\ CSL'99 local organization: & E-mail: csl99org(a)eucmos.sim.ucm.es \end{tabular} \end{minipage} \end{document}

1 0

Chew on this
by Michael Barr 25 Sep '98

25 Sep '98

Has anybody seen the following symmetric closed monoidal category? Let #A# be a category tripleable over Set. Let #V# be the comma category (F,#V#), F being the free functor. So an object (S,s,A) is an arrow s:FS --> A and a map (S,s,A) to (T,t,B) is a pair f: S --> T and g: A --> B making the obvious square commute. The closed structure (S,s,A) --o (T,t,B) is a certain arrow of the form (Hom((S,s,A),(T,t,B),?,B^S). The monoidal structure is fairly ugly, but it exists. Of course, an object (S,s,A) can also be thought of as an S-tuple of elements of A, by adjointness. Michael

2 1

URL update for Category group, Montreal (Lambek Festschrift, etc)
by R.A.G. Seely 23 Sep '98

23 Sep '98

Recently there have been some security problems with the Montreal Category Group's ftp site on triples. This seems a good opportunity to remind people that our old "ftp-based" URLs have been updated for WWW use. In particularly, the "official" URL for the group's WWW page is (and has been for a while now) http://triples.math.mcgill.ca (note the absence of the redundant "www" prefix) Related URLs that are linked to this include the recent call for papers for the Lambek Festschrift (deadline 31 Jan 1999) http://triples.math.mcgill.ca/lambek/LambekVol.html as well as the current seminars of the group, and the table of contents for the upcoming special issue of JPAA in honour of Mike Barr ("Barrfest"). http://triples.math.mcgill.ca/~rags/seminar/ http://triples.math.mcgill.ca/barrfest/bfpapers.html (and other links of interest...) The last time a note such as this went out, we promised to support the "old" urls for a time - that time may be running out now, so we encourage all interested to verify that your links and bookmarks are up-to-date in this regard. For the time being, any ftp to triples may be unreliable, until the security issues are resolved. = rags = (Robert Seely) <rags(a)math.mcgill.ca> <http://www.math.mcgill.ca/~rags>

1 0

BOUNCE categories@mta.ca: Approval required:
by Categories List 23 Sep '98

23 Sep '98

>>From rrosebru Wed Sep 23 02:05:51 1998 Received: from triples.math.mcgill.ca (rags(a)Triples.Math.McGill.CA [132.206.150.30]) by mailserv.mta.ca (8.8.8/8.8.8) with ESMTP id CAA12200 for <categories(a)mta.ca>; Wed, 23 Sep 1998 02:05:50 -0300 (ADT) Received: from localhost (rags@localhost) by triples.math.mcgill.ca (8.8.5/8.6.10) with SMTP id BAA00039; Wed, 23 Sep 1998 01:09:15 -0400 X-Authentication-Warning: triples.math.mcgill.ca: rags owned process doing -bs Date: Wed, 23 Sep 1998 01:09:15 -0400 (EDT) From: "R.A.G. Seely" <rags(a)math.mcgill.ca> To: Linear mailing list <linear(a)cs.stanford.edu>, Types List <types(a)cis.upenn.edu>, Categories List <categories(a)mta.ca> Subject: URL update for Category group, Montreal (Lambek Festschrift, etc) Message-ID: <Pine.LNX.3.95.980923005641.31750A-100000(a)triples.math.mcgill.ca> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Recently there have been some security problems with the Montreal Category Group's ftp site on triples. This seems a good opportunity to remind people that our old "ftp-based" URLs have been updated for WWW use. In particularly, the "official" URL for the group's WWW page is (and has been for a while now) http://triples.math.mcgill.ca (note the absence of the redundant "www" prefix) Related URLs that are linked to this include the recent call for papers for the Lambek Festschrift (deadline 31 Jan 1999) http://triples.math.mcgill.ca/lambek/LambekVol.html as well as the current seminars of the group, and the table of contents for the upcoming special issue of JPAA in honour of Mike Barr ("Barrfest"). http://triples.math.mcgill.ca/~rags/seminar/ http://triples.math.mcgill.ca/barrfest/bfpapers.html (and other links of interest...) The last time a note such as this went out, we promised to support the "old" urls for a time - that time may be running out now, so we encourage all interested to verify that your links and bookmarks are up-to-date in this regard. For the time being, any ftp to triples may be unreliable, until the security issues are resolved. = rags = (Robert Seely) <rags(a)math.mcgill.ca> <http://www.math.mcgill.ca/~rags>

1 0

ftp on triples
by Michael Barr 22 Sep '98

22 Sep '98

We have apparently had some kind of break-in on triples using the ftp demon. The only damage has been the downloading of enormous quantities of material. Enough to slow triples to a halt and also to get the computing centre upset enough to threaten to remove us from their net. Therefore, we have disabled anonymous ftp. I am now trying to find out if the material is available from the web and, if not, how to make it available. In any case, if there is something you need, please write and ask the author and s/he will undertake to email it to you. Later on, we will decide what to do. One possibility is to password protect it and announce the password on this list. This will protect us from random browsers, while leaving it available to all subscribers to this list. Michael

1 1

Symmetric monoidal closed comma categories
by F W Lawvere 20 Sep '98

20 Sep '98

This concerns the discussion by Mike Barr, Paul Taylor, and Masahito Hasegawa regarding symmetric monoidal closed comma categories: The construction (later called 'comma') in the category of categories was introduced in 1963 primarily for foundational simplification (though it was clear that certain particular cases, such as slice, were already in direct use). Besides the 2-categorical equational description of adjointness, one needs the description in terms of a bijection between arrows, but that does not require the complicated assumption that there exists a category of sets in which two given categories can be enriched. Namely, an adjunction between two given categories can be described by giving a third 'adjunction category', related by appropriate functors to them, which is isomorphic to two differently-constructed 'comma' categories. It seems that there are many cases in which this third category is of interest in itself, whether or not one of the two given categories is or is not monadic or comonadic over the other. Emilio Faro's notes from my Fall 1990 Buffalo course Categories of Space and of Quantity, mention essentially the result cited by Masahito Hasegawa. If an adjunction involves monoidal functors, then the adjunction category tends to be a monoidal closed category. This remark was essentially intended to supply semantically-based examples of closed categories which have one aspect which is linear (in the straightforward sense that coproducts equal products) and an opposite aspect which is cartesian (in the sense that the tensor is the categorical product). Of course, the most immediate subclass of examples, based on the data of a rig in a cartesian closed category, involve monadic adjunctions. On the other hand, several published papers on related matters axiomatically assume comonadic adjunctions. However, the simple algebraic stance, as Masahito Hasegawa points out, is that both aspects, as well as the relation between them, are all regarded as equally given. As part of the logic (= natural structure) of the resulting situation there will be unary (= modal?) operators reflected on each aspect by composing. A further step is to investigate to what extent the data can be approximated via data which is reconstructed on the basis of only one aspect or the other using this additional reflected structure. Both that step a la M. Stone, as well as the simple algebraic stance in the spirit of Chu and G. Mackey, are of course involved in the full study of any related pair of aspects (e.g. algebra and geometry). A problem from topology, where related considerations may help, concerns the operation of collapsing a connected subspace to a point (the effect of this operation on relative homology is part of the content of algebraic topology). In extending this operation to apply to not-necessarily-connected subspaces (and more generally, from inclusion maps to arbitrary maps), collapsing all these to a point would be an unnecessarily discontinuous functor. Rather, within the category whose objects are continuous maps, consider the subcategory wherein the domains of these structural maps are discrete (or zero-dimensional, if that is different in the model of continuity being considered). That subcategory is reflective (with the help of pushout) in case the model admits a left adjoint connected-components functor. In the case of a subspace, the reflector collapses each of its components to a distinct point in the new ambient space, and the lifted unit of the adjunction is epimorphic if the original one (to the connected components pi zero) is, even where the subspace is empty. I am wondering: under what conditions are these categories and functors cartesian monoidal closed? Indeed these things are probably folklore, but listed below are some references containing partial indications. Bill Functorial Semantics of Algebraic Theories Thesis Columbia University (1963) The Category of Categories as a Foundation for Mathematics, Proceedings of La Jolla Conference, Springer-Verlag (1966) 1 - 20 Categories of Space and of Quantity, Buffalo Course Notes by Emilio Faro (1990) ******************************************************************************* F. William Lawvere Mathematics Dept. SUNY wlawvere(a)acsu.buffalo.edu 106 Diefendorf Hall 716-829-2144 ext. 117 Buffalo, N.Y. 14214, USA *******************************************************************************

1 0

TLCA 99 : extended deadline
by Typed Lambda-Calculi and Applications 15 Sep '98

15 Sep '98

________________________ EXTENDED DEADLINE FOR TLCA 99 In order to respond to a popular demand, the PC of TLCA 99 has decided to accept late submissions, namely all papers arriving BEFORE Monday 28 September. Below is the updated call for papers. \documentstyle{article} \parindent 0cm \pagestyle{empty} \textwidth 18cm \textheight 28cm \topmargin -2.5cm \oddsidemargin -1.2cm \evensidemargin 0cm \begin{document} \begin{center} {\Large Fourth International Conference on} \end{center} \smallskip \begin{center} {\Huge Typed Lambda Calculi and Applications} \end{center} \begin{center} {\Huge (TLCA'99)} \\ \end{center} \bigskip \begin{center} {\Large l'Aquila (Italia), 7 to 9 April 1999} \end{center} \smallskip \begin{center} {\LARGE \bf Call For Papers} \end{center} \bigskip The TLCA series of conferences aims at providing a forum for the presentation and discussion of recent research in an area which was originally a rather restricted field but has now considerably expanded. The following list of topics is non-limitative:\\ \vspace{-0.4cm} {\large \begin{center} \begin{tabular}{@{}ll} {\bf Proof-theory} & {Cut-elimination and normalization, Linear logic, \ldots}\\ \\ {\bf Semantics} & {Denotational semantics, Game semantics, \ldots}\\ \\ {\bf Operationality} & {Abstract machines, Parallel execution, \ldots}\\ \\ {\bf Typing} & {Subtypes, Type assignment systems, \ldots}\\ \\ {\bf Programming} & {Proof search, Type checking, \ldots}\\ \end{tabular} \end{center} } \bigskip \begin{minipage}[t]{8.5cm} The programme of TLCA'99 will consist of about 30 selected presentations in plenary sessions. The Programme Committee consists of:\\ {\bf S.~Abramsky}~(University of Edinburgh) \\ {\bf T.~Coquand}~(G\"oteborgs Universitet) \\ {\bf J.-Y.~Girard}~(IML/Marseille) ({\bf Chair}) \\ {\bf R.~Hindley}~(University of Wales Swansea) \\ {\bf J.-L. Krivine}~(Universit\'e Paris VII) \\ {\bf J.~Reynolds}~(Carnegie-Mellon University/Pittsburgh) \\ {\bf S.~Ronchi}~(Universit\`a di Torino) \\ {\bf A.~Scedrov}~(University of Pennsylvania/Philadelphia) \\ {\bf T.~Streicher}~(Technische Universit\"at Darmstadt) \\ {\bf M.~Takahashi}~(T\^oky\^o K\^ogy\^o Daigaku) \\ {\bf P.~Urzyczyn}~(Uniwersytet Warszawski) \\ {\bf Original contributions} should be sent by E-mail (Postscript files only) to \begin{quote} tlca99(a)iml.univ-mrs.fr \end{quote} and a short abstract should be sent as a separate E-mail; it should use only standard ASCII characters. Hard copy (6 copies) is also acceptable, to the address \begin{quote} Jean-Yves Girard, \\ Institut de Math\'ematiques de Luminy, \\ 163 Avenue de Luminy, case 907, \\ 13288 Marseille cedex 9, France \\ {\bf fax:} (+)-33-491269655 \end{quote} All submissions must be {\bf received} by Sept. 27, 1998. \end{minipage} \hspace{1cm} \begin{minipage} [t]{8.5cm} Papers should not exceed 15 standard A4 or U.S. quarto pages and should allow the Programme Committee to assess the merits of the work: in particular references and comparisons with related work should be included. Submission of material already published or submitted to other Conferences with Proceedings is not allowed.\\ {\bf Relevant dates:} \begin{quote} Submissions: {\em September 4, 1998}\\ Acceptance/rejection: {\em November 16, 1998} \\ Definitive versions due: {\em January 4, 1999} \end{quote} The accepted papers will be published as a volume of Springer Lecture Notes in Computer Science. Information about LNCS can be found at the home page \vspace{-0.3cm} \begin{quote} http://www.springer.de/comp/lncs/index.html \end{quote} More details about the Conference will become available later from the Organizing Committee Chairman: \begin{quote} Benedetto Intrigila\\ Dipartimento di Matematica\\ Universit\`a di l'Aquila\\ Via Vetoio, Loc. Coppito\\ 67100 l'Aquila, Italia\\ {\bf E-mail:} tlca99.aquila(a)univaq.it\\ {\bf fax:} (+)-39-862-433180 \end{quote} or at the home page: \begin{quote} http://w3.dm.univaq.it/tlca99 \end{quote} \end{minipage} \end{document}

1 0

Barr's symmetric monoidal closed comma category
by Paul Taylor 15 Sep '98

15 Sep '98

Mike Barr asked whether anyone had been aware that the comma category (F,A) or equivalently (S,U) is symmetric monoidal closed, where A ^ | F| -| |U | V S is a monoidal (tripleable) adjunction over S=Set. As he said, an object (S,s,A) is an arrow s:FS--> A (or, by adjointness, an S-tuple of elements of A) and a map (S,s,A) to (T,t,B) is a pair f: S --> T and g: A --> B making the obvious square commute. He said that the closed structure (S,s,A) --o (T,t,B) is a certain arrow of the form (Hom((S,s,A),(T,t,B),?,B^S). I have certainly seen comma categories like (S,U); they are referred to as gluing, sconing or the Freyd cover. (BTW Peter says that "scone" is a corruption of Sierpinski cone, so its correct pronunciation is presumably "shco:ne".) This construction provides an almost magical proof of strong normalisation, consistency and similar results for various fragments of symbolic or categorical logic. The algebraic theory that I have in mind here for Mike's monadic adjunction is that which describes the fragment of logic in question (the Australians would prefer us to talk about a 2-monad here). An early example of such a proof in the unification of these two traditions was given by Yves Lafont in an appendix to his thesis. He proved that the embedding of a category in the free CCC that it generates is full and faithful. In the course of this he described the exponential in (S,U), which is what Mike's formula gives, though I didn't notice (and apparently nor did Yves) that the A-object which we have is the internal version of Mike's Hom-set. Yves Lafont's result appears as part of a generic account of the gluing construction in Section 7.7 of my forthcoming book. Paul

2 1

approaches to crypto
by Al Vilcius 14 Sep '98

14 Sep '98

Dear friends: has anyone in CT-land been thinking about cryptography? I'm looking for a structuralists' spin to the now classical approaches, primarily relating to public key cryptosystems as initiated by [DH'76], which complements the standard number theory approach [K'94]. In [D'88] Diffie suggests that abstractions which have proven to be useful in addressing many other classical problems will also be needed in crypto. Of course! The classical central problem is to find suitable "one-way" functions or algorithms: easy in one direction but "hard" in the other. Factoring is one example, as well as discrete logs in finite fields and groups of elliptic curves where the arithmetic is computationally difficult. A delightful survey (translated from German) is given in the little MAA monograph [B'94] by Beutelspacher, worth reading for its enjoyment alone. Provably secure cryptosystems do exist; this occurs when there is an iso between messages and random keys, although "truly random" is still problematic. However, these are not practical in general, and are not used commercially. Consequently, in trying to break cryptosystems, most approaches to the crypanalysis are analytic, focusing on digital computation. However I have this feeling that an "analogue" approach may be fruitful. After all, one of the most successful attacks to date is DPA (differential power analysis) [NYT'98] which is essentially an analogue or non-computational method of extracting keys and other information. But in addition to physical engineering methods, there may other logical analogue approaches such as quantum computing that might be useful, and arise categorically. The property that small changes in a message should result in large changes in the cryptogram may suggest some application of chaotic or non-linear dynamical systems. This has indeed been tried, but again on a mechanical rather than structural level. It feels like time should be fundamental (temporal thinking?) since that seems to provide the uniqueness to distinguish messages. However, this should also involve a deeper understanding of variation (perhaps via time sheaves) which might provide superior approaches in terms of thinking about crypto problems. An indication that crypto may be interesting to categorists is that protocols could be viewed in game theoretic terms, the latter having already been considered structurally. Furthermore, perhaps all attack scenarios can be formulated in game theoretic terms, hence also defense strategies. Another inspiration (at least to me) is induced by the nice treatment given by Steve Vickers to the example of bit strings as topological systems that threads through [V'89]. After all, 2-star-omega is the crypto base space. As a final inducement, it is worth noting that there is real money in this stuff. Commercial applications of crypto have great value in this security conscious information society of ours. Your thoughts would be most welcome, but no flames please. ... Al Vilcius (retread algebraist). References: [B'94] Albrecht Beutelspacher, "Crypyology", Mathematical Association of America, 1994 [D'88] Whitfield Diffie, "The First Ten Years of Public-Key Cryptograohy", Proc IEEE, Vol 76, No. 5, May 1988, pp.560-77 [DH'76] Whitfield Diffie and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol IT-22, No. 6, Nov 1976, pp. 644-54 [K'94] Neal Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag 1994 [NYT'98] "Cryptographers Discuss Finding Of Security Flaw in Smart Cards", New York Times, June 10, 1998 [V'89] Steven Vickers, "Topology via Logic", Cambridge UP 1989

1 0