From cat-dist Mon Feb 2 10:11:23 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA00914; Mon, 2 Feb 1998 10:11:13 -0400 (AST) Date: Mon, 2 Feb 1998 10:11:13 -0400 (AST) From: categories To: categories Subject: RE: sad news Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sat, 31 Jan 1998 23:49:46 -0500 (EST) From: Fred E J Linton On Fri, 30 Jan 1998 17:04:36 -0500 (EST) Peter Freyd wrote: > Sammy Eilenberg died today. As someone who had long secretly seen Sammy as a sort of second father figure, I am somewhat unnerved that the date of his death coincided so perfectly with what would have been exactly my mother's 102nd birthday. R.i.P. -- Fred From cat-dist Mon Feb 2 10:11:24 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA02072; Mon, 2 Feb 1998 10:10:14 -0400 (AST) Date: Mon, 2 Feb 1998 10:10:14 -0400 (AST) From: categories To: categories Subject: Re: Friedman's challenge, and the ordinals Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sat, 31 Jan 1998 16:21:53 +0000 (GMT) From: Dr. P.T. Johnstone Some comments on Paul Taylor's diatribe: > I have a personal reason for bitterly resenting ever being taught > set theory. (I don't want anybody to interpret that as resentment > towards the particular people in Cambridge who did the teaching - Thanks, Paul! > For several years I was trying to prove (in an elementary topos, > in particular without excluded middle, or the axiom of collection, > which seems to me to be set-theoretic hocus pocus): > Let (X, <=) be a poset with least element and directed > joins, and s:X->X a monotone (not necessarily Scott > continuous) function. Then s has a least fixed point. > I talked about my attempts at this at at least two international > category meetings and several other project meetings and conferences. > > Because of my set-theoretic indoctrination, much as I rebelled > against it, I set about defining ordinal iterates of the function s > and its values at the least element. Well, perhaps you should have been blaming me after all. I clearly never got around to teaching you Ernst Witt's amazing proof (Beweisstudien zum Satz von M. Zorn, Math. Nachr. 4 (1951), 434--438) of the existence of fixed points for an s:X->X which is merely assumed to be inflationary (i.e. x \leq s(x) for all x \in X), and not necessarily monotone. (Of course, you can recover the result for monotone s by restricting to the subset \{x\in X | x \leq s(x)\}.) [I may say that I didn't discover this paper for myself; it was brought to my notice by Bernhard Banaschewski (who had obvious reasons for knowing about it). It appears that Brian Davey and Hilary Priestley also knew about it, since they included it as Theorem 4.14 in their "Introduction to Lattices and Order" (C.U.P., 1990), though they don't attribute it to Witt (or to anyone else).] Witt's proof, like Pataraia's, is entirely order-theoretic and uses only naive set theory; it is clearly inspired by Zermelo's second proof of the well-ordering theorem, to which Paul referred. What it does use, however, is the Law of Excluded Middle, in a way which seems absolutely inextricable from the proof. Nevertheless, I suspect that an extremely clever person, trying to constructivize Witt's proof, could have discovered the idea of Pataraia's. (I didn't, although I spent some ten years thinking about the problem on and off; Pataraia didn't either -- he told me in November that he wasn't aware of Witt's proof.) > Pataraia's solution is pure order theory. You could teach it to > a third year undergraduate class in a course on lattices or domain > theory. Indeed you could. The same is true of Witt's proof: I did teach it, last term, in my third-year logic course here in Cambridge. (The students found it quite tough going, but they managed to swallow it -- I think.) A couple of weeks later I learned of Pataraia's proof at the Aarhus PSSL meeting; so the students got that too, immediately after I returned to Cambridge. (They must think I'm obsessed with this particular theorem; perhaps they're right.) There remains an open problem, however. Pataraia's proof is constructive (that is, it works in any topos -- though it is impredicative, so the Martin-L\"of people won't accept it), but it does require the function s to be monotone as well as inflationary. So: can anyone find a constructive proof of Witt's original result (without the monotonicity assuption)? Peter Johnstone From cat-dist Wed Feb 4 10:18:34 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA10503; Wed, 4 Feb 1998 10:17:21 -0400 (AST) Date: Wed, 4 Feb 1998 10:17:20 -0400 (AST) From: categories To: categories Subject: Sammy obits Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 3 Feb 1998 18:22:14 -0500 (EST) From: Peter Freyd Copyright 1998 The New York Times Company February 3, 1998, Tuesday, Late Edition - Final NAME: Samuel Eilenberg SECTION: Section B; Page 9; Column 1; Metropolitan Desk LENGTH: 660 words HEADLINE: Samuel Eilenberg, Dies; Mathematician at Columbia BYLINE: By ERIC PACE BODY: Samuel Eilenberg, an eminent mathematician and collector of Asian art, died on Friday at the Isabella Geriatric Center in upper Manhattan, where he had been for three months. He was 84 and had been a longtime resident of the Upper West Side of Manhattan. He had been in poor health for the last three years, said Robert L. Poster, one of the co-executors of his estate. Dr. Eilenberg retired in 1982 as a University Professor, the highest professorial rank, at Columbia University, where he had taught since 1947. He was born in Warsaw and moved in 1939 to the United States, where he became renowned for his work in the fields of algebraic topology and homological algebra. He served twice as chairman of Columbia's mathematics department, and taught at the University of Michigan from 1940 to 1946 and at the University of Indiana in 1946 and 1947. In 1986, he was a co-winner, with Atle Selberg of the Institute for Advanced Study at Princeton, of the $100,000 Wolf Foundation Prize in Mathematics. Beginning in the mid-1950's, Dr. Eilenberg amassed an art collection comprising many small sculptures and other artifacts, in bronze, silver, stone and other materials. The works were made between the 3d century B.C. and the 17th century in Indonesia, Pakistan, India, Nepal, Thailand, Cambodia, Sri Lanka and Central Asia. The collection came to be valued at more than $5 million. Then in 1987, he gave more than 400 artifacts from the collection to the Metropolitan Museum of Art, which put on a show of holdings from his collection, "The Lotus Transcendent: Indian and Southeast Asian Art From the Samuel Eilenberg Collection," in 1991 and 1992. In return for his generosity, the museum raised most of the $1.5 million necessary to create the Samuel Eilenberg Visiting Professorship of Mathematics at Columbia. Another member of Columbia's mathematics department, Prof. John W. Morgan, said, "The theme that runs through Sammy's mathematics is always to find the absolutely essential ingredients in any problem and work only with those ingredients and nothing else -- in other words, to get rid of all the superfluous information." When someone once asked Professor Eilenberg if he could eat Chinese food with three chopsticks, he answered, "Of course," according to Professor Morgan. The questioner asked, "How are you going to do it?" and Professor Eilenberg replied, "I'll take the three chopsticks, I'll put one of them aside on the table, and I'll use the other two." Dr. Eilenberg always applied that simplifying approach in his mathematical work, Professor Morgan said, and that helped him in his pioneering work in algebraic topology. In the 1930's, 40's and 50's, he was one of the main researchers in algebraic topology, the use of algebraic techniques to study problems involving shapes. Professor Eilenberg also helped develop a related field, homological algebra. He and a co-author, Prof. Norman E. Steenrod of Princeton University, collaborated in studying algebraic topology. They set out their findings in a 1952 book, "Foundations of Algebraic Topology" (Books on Demand), which is one of the primary sources in the field. The two mathematicians developed axioms, or rules, for analyzing objects through algebraic topology. "The Eilenberg-Steenrod axioms were crucial," Professor Morgan said, "in exposing the essential features of the constructions of algebraic topology." Professor Eilenberg's mathematical work in algebraic topology began in his native Warsaw in the mid-1930's, while he was studying at the University of Warsaw. He received his doctorate there in 1936. His many writings include the book "Homological Algebra" (Princeton, 1956) which he wrote with Henri Cartan. Professor Eilenberg received Guggenheim and Fulbright Fellowships and was a member of the American Academy of Arts and Sciences and other professional groups. His 1960 marriage to Natasha Chterenzon ended in divorce in 1969. GRAPHIC: Photo: Samuel Eilenberg (Columbia University) Copyright 1998 The Chronicle Publishing Co. The San Francisco Chronicle FEBRUARY 3, 1998, TUESDAY, FINAL EDITION SECTION: NEWS; Pg. A15; OBITUARIES LENGTH: 403 words HEADLINE: Samuel Eilenberg LINE: New York BODY: Samuel Eilenberg, eminent mathematician and collector of Asian art, died Friday. He was 84 and had been a longtime resident of the Upper West Side of Manhattan. Professor Eilenberg retired in 1982 as a university professor, the highest professorial rank, from Columbia University, where he had taught since 1947. He was born in Warsaw and moved in 1939 to the United States, where he became renowned for his work in the fields of algebraic topology and homological algebra. He served twice as chairman of Columbia's mathematics department, and taught at the University of Michigan from 1940 to 1946 and at the University of Indiana in 1946 and 1947. In 1986, he was a co-winner, with Atle Selberg of the Institute for Advanced Study at Princeton, of the $ 100,000 Wolf Foundation Prize in Mathematics. Beginning in the mid-1950s, Professor Eilenberg amassed an art collection comprising many small sculptures and other artifacts, in bronze, silver, stone and other materials. The works were made between the third century B.C. and the 17th century in Indonesia, Pakistan, India, Nepal, Thailand, Cambodia, Sri Lanka and Central Asia. The collection came to be valued at more than $ 5 million. In 1987, he gave more than 400 artifacts from the collection to the Metropolitan Museum of Art, which put on a show titled ''The Lotus Transcendent: Indian and Southeast Asian Art From the Samuel Eilenberg Collection,'' in 1991 and 1992. In return for his generosity, the museum raised most of the $ 1.5 million necessary to create the Samuel Eilenberg Visiting Professorship of Mathematics at Columbia. In the 1930s, '40s and '50s, he was one of the main researchers in algebraic topology, the use of algebraic techniques to study problems involving shapes. Professor Eilenberg also helped develop a related field, homological algebra. He and a co-author, Norman Steenrod of Princeton University, collaborated in studying algebraic topology. They set out their findings in a 1952 book, ''Foundations of Algebraic Topology'' (Books on Demand), which is one of the primary sources in the field. His many writings include the book ''Homological Algebra'' (Princeton, 1956) which he wrote with Henri Cartan. Professor Eilenberg received Guggenheim and Fulbright fellowships and was a member of the American Academy of Arts and Sciences and other professional groups. From cat-dist Fri Feb 6 14:45:25 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA17307; Fri, 6 Feb 1998 14:43:42 -0400 (AST) Date: Fri, 6 Feb 1998 14:43:42 -0400 (AST) From: categories To: categories Subject: Montebello on Eilenberg Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 6 Feb 1998 06:24:08 -0500 (EST) From: Peter Freyd Copyright 1998 The New York Times Company The New York Times February 6, 1998, Friday, Late Edition - Final SECTION: Section D; Page 19; Column 1; Classified LENGTH: 71 words HEADLINE: Paid Notice: Deaths EILENBERG, SAMUEL BODY: EILENBERG - Samuel. The Trustees and staff of The Metropolitan Museum of Art mourn the passing of Samuel Eilenberg, a longtime friend and Benefactor of the Museum. His generous gift of Indian and Southeast Asian works of art from a superb collection that he amassed over decades has greatly enhanced The Metropolitan's collections and will endure in the galleries for a grateful public. Philippe de Montebello, Director From cat-dist Fri Feb 6 14:45:29 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA21826; Fri, 6 Feb 1998 14:45:04 -0400 (AST) Date: Fri, 6 Feb 1998 14:45:04 -0400 (AST) From: categories To: categories Subject: on the NYUT Sammy obit Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 6 Feb 1998 10:59:03 -0500 (EST) From: F W Lawvere We noted that the Feb 3 New York Times description of Sammy Eilenberg's life contained notable ommissions, and in particular seriously under-represents the glorious achievements of the Columbia University Math Dept. Therefore we are sending the following letter to the Times, hoping that they'll print it. Editor: We were moved by your obituary of Professor Samuel Eilenberg, the eminent Columbia University mathematician. Our lives, like those of his many other students and colleagues around the world, were profoundly influenced by his 'insistence on getting to the bottom of things'. It is widely known in the mathematical community that Professor Eilenberg's most influential long-term collaboration was with the senior US mathematician Saunders Mac Lane, of the University of Chicago. Their joint discovery in 1945 of the theory of transformations between mathematical categories provided the tools without which Sammy's important collaborations with Steenrod and Cartan, which you mentioned, would not have been possible. That joint work laid also the basis for Sammy's pioneering work in theoretical computer science and for a great many continuing developments in geometry, algebra, and the foundations of mathematics. In particular, the Eilenberg-Mac Lane theory of categories was indispensable to the 1960 development, by the French mathematician Alexander Grothendieck, of the powerful form of algebraic geometry which was an ingredient in several recent advances in number theory, including Wiles' work on the Fermat theorem. Sincerely, Professor F. W. Lawvere, SUNY Buffalo Professor P.J. Freyd, University of Pennsylvania From cat-dist Fri Feb 6 17:53:07 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA13449; Fri, 6 Feb 1998 17:53:00 -0400 (AST) Date: Fri, 6 Feb 1998 17:53:00 -0400 (AST) From: categories To: categories Subject: CSL98 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 2 Feb 1998 15:23:24 +0100 (MET) From: Computer Science Logic Please accept our apologies if you receive this message more than once ----------------------------------------------------------------------- CSL '98 Annual Conference of the European Association for Computer Science Logic August 23-28, 1998 Brno, Czech Republic Federated CSL/MFCS Conference 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 topics significant for computer science. In 1998 the CSL conference will be organized as a joint event with MFCS (Mathematical Foundations of Computer Science). The federated CSL/MFCS conference will have common plenary sessions and common social program. Participants registering for one conference can attend talks of both conferences. Scientific Programme August 23, 1998: CSL Tutorials Lev Beklemishev (Russia): Inference Rules in Fragments of Arithmetic Peter Lee (USA): Proofs, Types, and Safe Mobile Code August 24--28, 1998: Invited Lectures and Contributed Papers The list of invited speakers will include: Joint CSL/MFCS plenary talks: D. Harel (Israel), W. Maass (Austria), Y. Matiyasevic (Russia), M. Yannakakis (USA) CSL invited speakers: P. Hajek (Czech Republic), J. Mitchell (USA), I. Nemeti (Hungary), Th. Schwentick (Germany), J. Tiuryn (Poland) MFCS invited speakers: G. Ausiello (Italy), E. Boerger (Italy), Y. Gurevich (USA), R. Karp (USA), T. Leighton (USA), K. Mehlhorn (Germany), S. Micali (USA), M. Nielsen (Denmark), A. Pnueli (Israel), P. Pudlak (Czech Republic), C. Stirling (UK), J.Wiedermann (Czech Republic) Submissions Authors are invited to submit a draft or full paper (up to 12 pages). The cover page should include title, authors, and corresponding authors (name, address, phone/fax number, e-mail address). Submission forms can be obtained from: http://www.dbai.tuwien.ac.at/CSL98/subm.html or by sending an empty message with Subject: submission information to: csl98-subm@dbai.tuwien.ac.at. Electronic submissions are encouraged. Alternatively, five hard copies should be received by April 15, 1998 by: Prof. Georg Gottlob, CSL '98 Institute of Information Systems TU Vienna Phone: +43 1 58801 6120 Paniglgasse 16 Fax: +43 1 5055304 A - 1040 VIENNA/AUSTRIA E-mail: csl98@dbai.tuwien.ac.at Authors will be notified of acceptance for presentation at the conference by June 18, 1998. A preliminary version of the full paper to be submitted to the proceedings volume (LNCS Springer-Verlag) should be available at the conference. Authors will be notified of acceptance of their paper by December 15, 1998. Program Committee: K. R. Apt (Netherlands) G. Gottlob (co-chair) (Austria) G. Longo (France) F. Baader (Germany) M. Kanovich (Russia) J. Paredaens (Belgium) A. Carbone(France) E. Grandjean (co-chair) (France) A. A. Razborov (Russia) T. Coquand (Sweden) C. Lautemann (Germany) A. Scedrov (USA) M. Fitting (USA) A. Leitsch (Austria) K. Stroetmann (Germany) A. Goerdt (Germany) D. Leivant (USA) A. Voronkov (Sweden) EACSL Board: M. Bezem, I. Stewart, C. Lautemann, P. Hajek, S. Martini, E. Palmgren, Ch. Paulin, A. Razborov, M. Vardi From cat-dist Fri Feb 6 17:54:04 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA20689; Fri, 6 Feb 1998 17:54:03 -0400 (AST) Date: Fri, 6 Feb 1998 17:54:03 -0400 (AST) From: categories To: categories Subject: NMR Workshop Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 3 Feb 1998 09:52:19 +0100 From: Juergen Dix Call for Papers: Please visit http://www.uni-koblenz.de/~dix/NMR7/ which is a part of the NMR '98 Workshop (CFP below). \documentstyle[12pt]{article} \textwidth=150mm \textheight=8.4in \hoffset=-.4in \voffset=-.6in \pretolerance 1000 \pagestyle{empty} \begin{document} \begin{center} { \LARGE {\bf Seventh International Workshop on \\ Nonmonotonic Reasoning} } \end{center} \begin{center} {\LARGE \bf NM'98} \end{center} \begin{center} \hspace{.2in} {\bf Trento, Italy, May 30 - June 1, 1998 \\ in conjunction with KR'98} \end{center} \begin{center} {\em Organizers:} \\ Ray Reiter (Honorary Chair) \\ Gerhard Brewka (Co-Chair) \\ Ilkka Niemel\"{a} (Co-Chair) \\ Enrico Giunchiglia (Local Chair) \end{center} The aim of the workshop is to bring together active researchers interested in the area of nonmonotonic reasoning to discuss current research, results, and problems of both theoretical and practical nature. The format of this workshop is different from earlier nonmonotonic reasoning workshops. NM'98 will consist of five specialized one day workshops to be held at least partly in parallel. The specialized workshops will be surrounded by a plenary program consisting of invited talks and panels. The following specialized workshops are part of NM'98: \begin{itemize} \item {\bf Formal Aspects and Applications of Nonmonotonic Reasoning} \\ Chairs: Jim Delgrande, Mirek Truszczynski \item {\bf Computational Aspects of Nonmonotonic Reasoning} \\ Chairs: Ilkka Niemel\"{a}. Torsten Schaub \item {\bf Logic Programming} \\ Chairs: J\"{u}rgen Dix, Jorge Lobo \item {\bf Action and Causality} \\ Chairs: Vladimir Lifschitz, Hector Geffner \item {\bf Belief Revision} \\ Chairs: Hans Rott, Mary-Anne Williams. \end{itemize} Submission of papers is {\em through the specialized workshops only}. The deadline for submissions is {\bf Feb. 23, 1998}. Participation is by invitation only. Those wishing to attend without submitting a paper should send a statement of interest with a short description of research interests and recent work to one of the co-chairs (brewka@informatik.uni-leipzig.de, ini@invariant.hut.fi) For more information and more detailed submission requirements contact our web-site at http://saturn.hut.fi/$\sim$ini/nmrw98.html. \end{document} From cat-dist Sun Feb 8 12:38:52 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id MAA15936; Sun, 8 Feb 1998 12:38:08 -0400 (AST) Date: Sun, 8 Feb 1998 12:38:08 -0400 (AST) From: categories To: categories Subject: Categorification Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Sat, 7 Feb 1998 16:00:14 -0800 (PST) From: john baez Here is the abstract of a paper that is now available at my website. ---------------------------------------------------------------------- Categorification John C. Baez and James Dolan To appear in Proceedings of the Workshop on Higher Category Theory and Mathematical Physics at Northwestern University, Evanston, Illinois, March 1997, eds. Ezra Getzler and Mikhail Kapranov. Categorification is the process of finding category-theoretic analogs of set-theoretic concepts by replacing sets with categories, functions with functors, and equations between functions by natural isomorphisms between functors, which in turn should satisfy certain equations of their own, called `coherence laws'. Iterating this process requires a theory of `n-categories', algebraic structures having objects, morphisms between objects, 2-morphisms between morphisms and so on up to n-morphisms. After a brief introduction to n-categories and their relation to homotopy theory, we discuss algebraic structures that can be seen as iterated categorifications of the natural numbers and integers. These include tangle n-categories, cobordism n-categories, and the homotopy n-types of the loop spaces Omega^k S^k. We conclude by describing a definition of weak n-categories based on the theory of operads. ----------------------------------------------------------------------- The paper is available in Postscript form on the web at http://math.ucr.edu/home/baez/cat.ps I can also email or snailmail you a copy at your request. From cat-dist Mon Feb 9 17:28:47 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA07252; Mon, 9 Feb 1998 17:27:47 -0400 (AST) Date: Mon, 9 Feb 1998 17:27:47 -0400 (AST) From: categories To: categories Subject: formal languages fibrationally Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 9 Feb 1998 09:39:06 +0100 (MET) From: Koslowski Dear Colleagues, Has anyone come across or have any interest in the following fibrational formulation of formal language theory? This is an observation of Robin Cockett during his recent visit to Braunschweig. Let T be the list monad on set and let set_T be the corresponding Kleisli category. Consider the functor from (set_T)^op to ord that maps a set_T-morphism A --f-> B (i.e., a set-function A --f-> T(B)=B^*) to the inverse image function from the power set of B^* to the power set of A^* (ordered by inclusion) induced by the unique extension \bar f of f. It corresponds to a bi-fibration lang --U-> set_T. The objects of the category lang are pairs with V a set and L\inc V^* a language over V. A lang morphism from to is a set_T-morphism V --h-> W subject to the requirement that L be contained in the inverse image of M under \bar h, or equivalently, that the direct image of L under \bar h be contained in M. Recall that a language L\inc V^* is of type 0, if it is generated by some grammar, 1, it it is generated by a context-sensitive grammar, 2, it it is generated by a context-free grammar, 3, if it is generated by a regular grammar. Now we may consider the subcategories lang_i of lang, 0<=i<=3, where the languages have to be of type i. Standard results of formal language theory tell us that for i\in\{0,2,3\} the restriction of U to lang_i still is a bi-fibration, while the restriction of U to lang_1 still is a fibration, but not a cofibration, since homomorphic images of type-1 languages need not be of type 1. For type-2 languages, a theorem of Greibach states the existence of a universal such, i.e., a context-free language L_{gr} such that every other context-free language is a homomorphic pre-image of L_{gr}. ([HK] has a construction of L_{gr} over a 7-element alphabet, but then one can of course find another such universal context-free language over a 2-element alphabet.) References: [G] Sheila A. Greibach: The hardest context-free language. SIAM J. Comput. 2(4) December 1973, 304--310 [HK] G"unter Hotz and Thomas Kretschmer: The power of the Greibach normal form. J. Inf. Process. Cybern. EIK 25 (10) 1989, 507--512 -- J"urgen Koslowski % If I don't see you no more in this world ITI % I meet you in the next world TU Braunschweig % and don't be late! koslowj@iti.cs.tu-bs.de % Jimi Hendrix (Voodoo Child) From cat-dist Mon Feb 9 17:28:50 1998 Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA30709; Mon, 9 Feb 1998 17:28:26 -0400 (AST) Date: Mon, 9 Feb 1998 17:28:26 -0400 (AST) From: categories To: categories Subject: Specification vs execution Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mailserv.mta.ca id RAA30709 Status: O X-Status: Date: Mon, 09 Feb 1998 15:13:29 +0100 From: Matthieu Amiguet Hello! I'm trying to learn category theory and understand its links to computer science. One of my big questions is: Is category theory a wonderful specification language, or is there any executable stuff in it ? All I've seen about application until now is specification or semantics (which is already a lot!) but I wonder if anything else was ever done. Thank you for any direct answer or any pointer to good texts about this. Matthieu Amiguet IIIA University of Neuchâtel (Switzerland) From espinosa@kestrel.edu Wed Feb 11 16:20:04 1998 Received: from kestrel.kestrel.edu (root@ws103.kestrel.edu [206.159.212.104]) by mailserv.mta.ca (8.8.8/8.8.8) with SMTP id QAA05340 for ; Wed, 11 Feb 1998 16:19:34 -0400 (AST) Received: from blackhawk.kestrel.edu by kestrel.kestrel.edu (4.1/SMI-DDN) id AA23262; Wed, 11 Feb 98 12:19:21 PST Received: by blackhawk.kestrel.edu (SMI-8.6/SMI-SVR4) id MAA05022; Wed, 11 Feb 1998 12:19:08 -0800 Date: Wed, 11 Feb 1998 12:19:08 -0800 Message-Id: <199802112019.MAA05022@blackhawk.kestrel.edu> From: David Espinosa To: categories@mta.ca Cc: espinosa@kestrel.edu Subject: decompositions of topoi Status: RO X-Status: Page 216 of Lambek and Scott describes how to decompose a topos via a cocover, that is, a monomorphism in Top M : T -> prod(i in I) T/P_i where P_i are the prime filters of T. (1) Does anyone know where to find a more extended discussion of this decomposition? (2) Is there a dual decomposition via a cover, that is, an epimorphism E : sum(i in I) T_i -> T ? This construction could already be in Lambek and Scott, but I haven't had the chance to study L&S in detail, so I'm still in over my head. The conjecture (due to Y.V. Srinivas) is that these ideas are useful for structuring a database of theories by breaking theories into their smallest reasonable subtheories. See the paper on Specware by Srinivas and Jullig on Kestrel's website http://www.kestrel.edu for more information. So far, this work has dealt with covers of theories, rather than cocovers, whence my question. David Espinosa Kestrel Institute From cat-dist Fri Feb 13 00:36:53 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id XAA05970 for categories-list; Thu, 12 Feb 1998 23:39:35 -0400 (AST) Message-Id: <199802130339.XAA05970@mailserv.mta.ca> X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Thu, 12 Feb 1998 23:35:29 -0400 (AST) From: Bob Rosebrugh Reply-To: Bob Rosebrugh To: categories Subject: New list server Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: With the previous post the categories list inaugurated use of a `majordomo' list service. This should result in little visible change for users of the list, and many of you will undoubtedly be familiar with majordomo list serves. Note that the From: field of a categories posting will now be the original sender. The list will continue to be moderated of course and archives will be maintained as before. As a reminder, mail for posting to categories should be sent to categories@mta.ca while administrative items go to categories-request@mta.ca Those of you who have aliases and so on that point to cat-dist@mta.ca for the categories list should change these to the first address mentioned above. Mail to cat-dist@mta.ca will have to be returned for reposting. For further information send a message to majordomo@mta.ca with a message body consisting of the word help Please contact me directly in case of any problem. Regards to all, Bob Rosebrugh From cat-dist Fri Feb 13 17:06:38 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA14900 for categories-list; Fri, 13 Feb 1998 15:41:33 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 13 Feb 1998 09:12:18 -0800 Message-Id: <199802131712.JAA10069@blackhawk.kestrel.edu> From: David Espinosa To: categories@mta.ca Cc: espinosa@kestrel.edu Subject: CATS Are primes ever generators? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: We can say that an object P in a category with coproducts is *prime* if whenever f : P -> A+B, f factors through one of the injections into A+B. (1) I didn't find any reference to this (obvious) notion of primality in the standard texts. Does it occur anywhere? (2) Is there any condition on the category under which the set of primes is a generating family? Since objects are decomposable into a "quotient of a coproduct of generators" (Borceux, volume 1, page 151), this would give a decomposition into primes. Thanks, David From cat-dist Fri Feb 13 17:25:03 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA22388 for categories-list; Fri, 13 Feb 1998 15:40:45 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <16940.199802131505@craro.dcs.ed.ac.uk> To: categories@mta.ca, types@cs.indiana.edu, theorynt@vm1.nodak.edu cc: als@dcs.ed.ac.uk, a.drizo@ed.sac.ac.uk Subject: CATS PhD Studentship at Edinburgh Date: Fri, 13 Feb 1998 15:05:38 +0000 From: Alex Simpson Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Department of Computer Science University of Edinburgh Announcement of PhD Studentship in Categorical Logic in Denotational Semantics A PhD student is sought for three years from October 1998 to work under the supervision of Dr. Alex Simpson on an EPSRC-funded project: Categorical Logic and Structure in Denotational Semantics. The project will apply category theory to axiomatize the essential structure of denotational models of programming languages. The student will work on the derivation of program logics from category-theoretic axiomatizations, and on the proof-theoretical analysis of such logics. The studentship is for three years and pays for all fees and includes maintenance (living expenses) at the usual EPSRC rate. The studentship will be held at the Laboratory for Foundations of Computer Science (LFCS), Department of Computer Science, University of Edinburgh. The LFCS provides an ideal environment for postgraduate research. The first six months of postgraduate training are supported by a unique postgraduate course on the theory of computation. In addition, there are regular short courses on advanced research topics, and a number of forums provide weekly research seminars. The LFCS is particularly strong in the area of semantics of programming languages. The PhD studentship is relevant to computer science or mathematics graduates who are interested in at least one topic from: theory of computation, denotational semantics, logic, category theory. For additional information contact Alex Simpson: Alex.Simpson@dcs.ed.ac.uk http://www.dcs.ed.ac.uk/home/als/ For an application form write to Eleanor Kerse PhD Admissions, Department of Computer Science, University of Edinburgh, JCMB, King's Buildings, Edinburgh EH9 3JZ Scotland or use the HTML form available from http://www.dcs.ed.ac.uk/deptinfo/admissions/phd ----------------------------------------------------------------------------- Alex Simpson, Email: Alex.Simpson@dcs.ed.ac.uk LFCS, Department of Computer Science, University of Edinburgh, JCMB, The King's Buildings, Mayfield Road, Tel: +44 (0)131 650 5113 Edinburgh, EH9 3JZ, UK. Fax: +44 (0)131 667 7209 URL: http://www.dcs.ed.ac.uk/home/als/ FTP: ftp.dcs.ed.ac.uk/pub/als From cat-dist Fri Feb 13 17:02:30 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA10363 for categories-list; Fri, 13 Feb 1998 15:08:39 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 13 Feb 1998 14:12:02 -0400 (AST) From: Bob Rosebrugh To: categories Subject: CATS Re: New list server Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Several subscribers have suggested subject lines for categories postings indicate that they originate with the list, so the first word will always be CATS. I should have pointed out that `categories-request@mta.ca' is now automated and will only handle listserv commands such as unsubscribe categories your.name@your.domain or subscribe categories your.name@your.domain (non-listserve commands will result in your message bouncing) So a change of email address requires using these two commands; anything else can still be sent directly to me at rrosebrugh@mta.ca Bob Rosebrugh From cat-dist Sat Feb 14 15:15:28 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id NAA17470 for categories-list; Sat, 14 Feb 1998 13:47:52 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 13 Feb 1998 17:40:06 -0800 Message-Id: <199802140140.RAA11783@blackhawk.kestrel.edu> From: David Espinosa To: categories@mta.ca Cc: espinosa@kestrel.edu Subject: CATS Categorical model for Floyd-Hoare logic? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Hopefully this is my last question for a while. Has there been work on a categorical model for "while programs" (or, equivalently, assembly language) and Floyd-Hoare logic? In the obvious model, objects are predicates on a store, and arrows are code sequences mapping stores to stores that satisfy the postcondition assuming the precondition. I'm interested to know: (1) What is the structure of this category? Does it have products, sums, etc? What program constructs do they correspond to? (2) What is the correct equality on arrows? I would think that we want the finest equality that yields nice structure. Then we can collapse afterward to obtain coarser categories. David From cat-dist Sat Feb 14 15:42:20 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id OAA31785 for categories-list; Sat, 14 Feb 1998 14:39:59 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sat, 14 Feb 1998 18:30:29 GMT Message-Id: <199802141830.SAA13270@sun4.mcs.le.ac.uk> From: "Roy L. Crole" To: categories@mta.ca Subject: categories: CATS Re: Categorical model for Floyd-Hoare logic? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: There is some work by Paul Taylor on categorical models of while in Theory and Formal Methods 1993, Springer Workshops in Computing, p302 on. Roy Crole From cat-dist Sun Feb 15 11:18:55 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA30139 for categories-list; Sun, 15 Feb 1998 10:07:52 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <199802142041.MAA21284@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: CATS Categorical model for Floyd-Hoare logic? In-reply-to: Your message of "Fri, 13 Feb 1998 17:40:06 -0800." <199802140140.RAA11783@blackhawk.kestrel.edu> Date: Sat, 14 Feb 1998 20:41:25 +0000 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: >Has there been work on a categorical model for "while programs" (or, >equivalently, assembly language) and Floyd-Hoare logic? The first such was developed by Arbib and Manes in the mid-70's. Manes went on to develop the theory in great detail, writing a near-book-length article on it a decade later, not sure where it appeared. (1) What is the structure of this category? As I recall it was an additive (semiadditive?) category, with sequential composition represent by composition, and choice by sum within homsets. The objects were predicates, the arrows were programs (aka predicate transformers). Does it have products, sums, etc? What program constructs do they correspond to? Not sure about products, but it certainly had sums. which was how if-then-else was handled. (2) What is the correct equality on arrows? My recollection is that it was fully abstract: the correct equality is equality. Vaughan Pratt From cat-dist Sun Feb 15 11:18:58 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA06607 for categories-list; Sun, 15 Feb 1998 10:08:33 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: esik@inf.u-szeged.hu Message-Id: <199802151144.HAA09888@mailserv.mta.ca> Date: Sun, 15 Feb 98 12:43 MET To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: >From esik Sun Feb 15 12:43:53 +0100 1998 remote from inf.u-szeged.hu To: categories@mta.ca cc: esik Subject: CATS Re: Categorical model for Floyd-Hoare logic Date: Sun, 15 Feb 1998 12:43:53 +0100 From: Esik Zoltan Received: from inf.u-szeged.hu by inf.u-szeged.hu; Sun, 15 Feb 1998 12:43 MET Content-Type: text Content-Length: 561 > Has there been work on a categorical model for > "while programs" (or,equivalently, assembly > language) and Floyd-Hoare logic? The books E.G. Manes: Predicate Transformer Semantics, Cambridge University Press, 1992 S.L. Bloom and Z. Esik: Iteration theories, Springer, 1993 (see in particular chapter 12 and 14) and the paper S.L. Bloom and Z. Esik: Floyd-Hoare logic in iteration theories, JACM, 38(1991), 887--934 consider such models. The books also contain references to other papers (including papers by Elgot and others). Zoltan Esik From cat-dist Mon Feb 16 12:55:15 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA30927 for categories-list; Mon, 16 Feb 1998 10:05:53 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sun, 15 Feb 1998 18:05:35 GMT From: Paul Taylor Message-Id: <199802151805.SAA16718@wax.dcs.qmw.ac.uk> To: categories@mta.ca Subject: categories: correction Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: > My motication (in 1987 this was) This should have been 1984 (and motivation). I'd also like to add: I had some difficulty in getting my ideas about stable coequalisers across (partly, of course, my fault, because I didn't get the rigt answer, involving stable transitive closures, until 1993). People said, "while programs can't possibly be described by finitary first order theories, because the theory of the natural numbers is an example". I knew that, and it wasn't what I meant. This illustrates a subtlely in first order categorical logic: that the relevant structure consists of *less* than all finite (limits and) stable disjoint colimits. The categorical structure corresponding to first order logic is a (Heyting) pretopos, which need not have coequalisers of arbitrary parallel pairs. For example, the category of compact Hausdorff spaces is a pretopos but does not have all stable coequalisers. (I have a feeling I haven't got this quite right, and Peter Freyd is going to jump on me. I shouldn't be so foolish as to answer mathematical questions on the modem from home!) More recently, Jiri Rosicky and Peter Johnstone have considered the question of what theories can be expressed with finite sketches. As Peter Freyd showed in 1972, this includes the natural numbers. My results and those of Jiri and Peter are more complicated forms of Peter Freyd's original observation. Finally, since my more recent work on categorical recursion, I no longer think that a coequaliser diagram is the best way of presenting a WHILE program categorically (though the diagram I would use now expresses the same logical content). Paul From cat-dist Mon Feb 16 13:08:09 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA16515 for categories-list; Mon, 16 Feb 1998 10:06:11 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 16 Feb 1998 10:21:38 +1100 (EST) Message-Id: <199802152321.KAA06612@algae.socs.uts.EDU.AU> From: Barry Jay To: categories@mta.ca In-reply-to: <199802141830.SAA13270@sun4.mcs.le.ac.uk> (R.Crole@mcs.le.ac.uk) Subject: Re: categories: CATS Re: Categorical model for Floyd-Hoare logic? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: A semantics of loops (and while-loops) where objects are types (not predicates) can be found in @InProceedings(Jay91d, Author={Jay, C.B.}, Title={Fixpoint and loop constructions as colimits}, Booktitle="Proceedings Summer Conference on Category Theory, Como 1990", Editor="A.~Carboni, M.C.~Pedicchio and G.~Rosolini", Series=Lecture Notes in Mathematics, Volume=1488, Publisher=sv, Year=1991, Pages={187--192}) and their use to account for tail-recursion is in @Article(Jay93a, Author={Jay, C.B.}, Title={Tail recursion through universal invariants}, Journal=Theoretcial Computer Science, Volume=115, Year=1993, Pages={151--189}) Barry Jay From cat-dist Mon Feb 16 13:28:02 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA26660 for categories-list; Mon, 16 Feb 1998 10:05:16 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sun, 15 Feb 1998 14:48:43 GMT From: Paul Taylor Message-Id: <199802151448.OAA16265@wax.dcs.qmw.ac.uk> To: categories@mta.ca Subject: categories: Categorical model for Floyd-Hoare logic? Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: I see Roy Crole has already answered this question on my behalf. The paper to which he refers is called "An Exact Interpretation of While" and is "while-1993.dvi.gz" on my page at Hypatia http://hypatia.dcs.qmw.ac.uk/author/TaylorP Manes' appraoach, as I recall, looks a bit like matrix algebra, with finite addition replaced by infinite union. From a programming point of view this seems to me like replacing a WHILE program (which doesn't know a priori how many times it is going to go round) with an infinite SWITCH/CASE statement indexed by the number of iterations. My motication (in 1987 this was) was that it only takes finitely many characters to write the program, so its semantics should be given in a finitary form. The bit of the (categorical) diagram which does the work is a coequaliser, and Barry Jay observed independently that this says in categorical language that the WHILE program is the "universal loop invariant". The coequaliser is not the whole story. It does not say when to exit the loop: some modifications to the diagram using pullbacks are needed. Nor will coequalisers in any old category do (cd the need for at least distributive and preferably extensive categories for if-then-else). I spent a long time trying to formulate the need for "stable" coequalisers correctly, but this never worked. It was necessary to fall back on stability of the formation of transitive or equivalence closures. There is a completely rewritten account of my work on WHILE programs in Section 6.4 of my book (not yet, I'm afraid, finished). The category theory does not match up quite as nicely as one would like ("full abstraction") for WHILE or even IF-THEN-ELSE. (The interpretation is sound, but what I know about it falls short of the equivalence which exists, for example, between lambda calculus and CCCs). My treatment of Floyd-Hoare logic is done in the greatest detail for what I call the direct declarative language (with assignments but no conditionals or loops). This is integrated with the categorical account of algebraic or finite-product theories. I now think I can motivate the definition of category and product EASIER on the basis of programming than from traditional mathematics. Floyd-Hoare logic & algebraic theories are in Chapter IV, conditionals in Section 5.5. Paul PS Yes, I know I've got to get this book finished. There are just not enough hours in the day! From cat-dist Mon Feb 16 13:40:10 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id KAA21238 for categories-list; Mon, 16 Feb 1998 10:06:28 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 16 Feb 1998 10:26:09 +1100 (EST) Message-Id: <199802152326.KAA16703@milan.maths.su.oz.au> From: Steve Lack To: espinosa@kestrel.edu CC: categories@mta.ca, espinosa@kestrel.edu In-reply-to: <199802131712.JAA10069@blackhawk.kestrel.edu> (message from David Espinosa on Fri, 13 Feb 1998 09:12:18 -0800) Subject: categories: Re: CATS Are primes ever generators? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f > Date: Fri, 13 Feb 1998 09:12:18 -0800 > From: David Espinosa > Cc: espinosa@kestrel.edu > Precedence: bulk > > > > We can say that an object P in a category with coproducts is *prime* > if whenever f : P -> A+B, f factors through one of the injections into > A+B. > > (1) I didn't find any reference to this (obvious) notion of > primality in the standard texts. Does it occur anywhere? > > (2) Is there any condition on the category under which the set of > primes is a generating family? Since objects are decomposable > into a "quotient of a coproduct of generators" (Borceux, volume 1, > page 151), this would give a decomposition into primes. > > Thanks, > > David > > > Dear David, One convenient setting for your question is provided by _extensive_ categories (see the paper ``Introduction to extensive and distributive categories'' by Carboni, Lack, and Walters, appearing in JPAA 1993). A category E with finite coproducts is said to be extensive if for all objects x,y of E, the ``coproduct functor'' E/x x E/y --> E/(x+y) is an equivalence. For such a category E, an object p is prime in your sense if and only if it is connected, i.e. if and only if it admits no proper coproduct decomposition; this in turn is equivalent to the representable functor E(p,-):E-->Set preserving coproducts. An example of an extensive category is given by Fam(C) for C a (small) category. The objects of Fam(C) are finite families (C_i)_{i\in I} and an arrow from (C_i)_I to (D_j)_J comprises a function f:I-->J and a family of arrows C_i-->D_fi in C. Fam(C) is the free category with finite coproducts on the category C. The connected (=prime) objects are precisely the singleton families. One can characterize the categories of the form Fam(C) as those extensive categories with a small set of connected objects such that every object is a finite coproduct of connected objects. (It seems possible that you could replace ``extensive'' in the last sentence by ``category with finite coproducts'' provided that you also replace ``connected'' by ``prime and connected'', but I haven't thought about this.) Best wishes, Steve. From cat-dist Mon Feb 16 18:26:01 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA30768 for categories-list; Mon, 16 Feb 1998 17:17:15 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Subject: categories: CATEGORY THEORY WORKSHOP From: rjwood@mscs.dal.ca To: categories@mta.ca Date: Mon, 16 Feb 1998 15:23:08 -0400 (AST) X-Mailer: ELM [version 2.4 PL24alpha3] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-Id: <19980216192310Z82695-267+3@mscs.dal.ca> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: ANNOUNCEMENT WORKSHOP In conjunction with the Category Theory Symposium at the Canadian Mathematical Society's (Northern) Summer 1998 Meeting, there will be a workshop on the Applications of Category Theory to Computer Science, directed towards graduate students and young researchers. June 8-12, 1998 (arrival day Sunday, June 7,1998) Mount Allison University (home of CATEGORIES and TAC) Sackville, New Brunswick, Canada The invited instructors are M. Barr (McGill) and R.F.C. Walters (Sydney). Residence accommodation will be available at Mount Allison University at a cost of $27.60/person/night for a single room $24.30/person/night for a shared double room $23.00/person/night for either of the above for students upon presentation of a student card. (All prices are in Canadian dollars and include taxes.) Bookings can be made at http://www.mta.ca/conference/overnigh.htm There will be a registration fee of $50 for the workshop. To preregister send e-mail to ct95@mscs.dal.ca (sic) with subject heading `workshop'. On the evening of Friday June 12 the Workshhop participants will receive free transportation to Saint John, New Brunswick, site of the aforementioned Category Theory Symposium. Sponsored by The Fields Institute for Research in Mathematical Sciences and AARMS, The Atlantic Association for Research in the Mathematical Sciences From cat-dist Mon Feb 16 18:43:30 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id RAA00266 for categories-list; Mon, 16 Feb 1998 17:16:56 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Subject: categories: CATEGORY THEORY SYMPOSIUM From: rjwood@mscs.dal.ca To: categories@mta.ca Date: Mon, 16 Feb 1998 15:21:33 -0400 (AST) X-Mailer: ELM [version 2.4 PL24alpha3] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-Id: <19980216192140Z82695-265+9@mscs.dal.ca> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: ANNOUNCEMENT CATEGORY THEORY SYMPOSIUM A special session of the Canadian Mathematical Society Summer 1998 Meeting June 13-15, 1998 University of New Brunswick (Saint John) Saint John, New Brunswick, Canada The symposium follows the usual format found at society meetings in North America. Thus it is part of a larger programme including plenary talks, one of which will be given by S. Schanuel (SUNY Buffalo). The larger programme also features a public lecture by F.W. Lawvere (SUNY Buffalo). The invited speakers for the Category Theory Symposium are M. Barr (McGill), M. Bunge (McGill), P. Freyd (Pennsylvania), A.Joyal (UQAM), F.W. Lawvere (SUNY Buffalo), M. Makkai (McGill), S. Niefield (Union), R. Pare (Dalhousie), J.W. Pelletier (York), S. Schanuel (SUNY Buffalo), M. Tierney (Rutgers), W. Tholen (York), and R.F.C. Walters (Sydney). Registration for the meeting, including fees, is handled by the Canadian Mathematical Society (CMS). A pre-registration form can be obtained by writing to meetings@cms.math.ca Electronic pre-registration is available on the CMS site at http://camel.math.ca/CMS/Events/summer98 At this site complete information about all necessities, such as accommodation, is provided. However, category theorists who plan to attend are strongly urged to also send e-mail to ct95@mscs.dal.ca (sic) where it will be readily available to RJ Wood (Dalhousie), Category Theory Session Organizer and Robert Rosebrugh (Mount Allison), Meeting Director From cat-dist Tue Feb 17 18:10:23 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA23127 for categories-list; Tue, 17 Feb 1998 16:19:31 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: maxk@maths.usyd.edu.au Date: Tue, 17 Feb 1998 15:27:18 +1100 (EST) Message-Id: <199802170427.PAA18919@milan.maths.su.oz.au> To: adamek@iti.cs.tu-bs.de, borceux@agel.ucl.ac.be, categories@mta.ca, lics-owner@research.bell-labs.com Subject: categories: email address Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Please note that my old email address kelly_m@maths.su.oz.au is soon to be obsolete, and should be replaced by maxk@maths.usyd.edu.au Regards - Max Kelly. From cat-dist Thu Feb 26 23:52:00 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id WAA21381 for categories-list; Thu, 26 Feb 1998 22:07:44 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 24 Feb 1998 14:18:32 GMT From: Samin Ishtiaq Message-Id: <199802241418.OAA21711@wax.dcs.qmw.ac.uk> To: categories@mta.ca Subject: categories: new paper: A Relevant Analysis of Natural Deduction Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: We apologize for multiple copies of this mail. The following paper will appear in the Journal of Logic and Computation (expected in Vol. 8) later this year: A Relevant Analysis of Natural Deduction S Ishtiaq and DJ Pym Queen Mary and Westfield College University of London {si,pym}@dcs.qmw.ac.uk We study a framework, RLF, for defining natural deduction presentations of linear and other relevant logics. RLF consists in a language together, in a manner similar to that of LF, with a representation mechanism. The language of RLF, the $\lambda\Lambda_{\kappa}$-calculus, is a system of first-order linear dependent function types which uses a function $\kappa$ to describe the degree of sharing of variables between functions and their arguments. The representation mechanism is judgements-as-types, developed for linear and other relevant logics. The $\lambdal\Lambda_{\kappa}$-calculus is a conservative extension of the $\lambda\Pi$-calculus and RLF is a conservative extension of LF. The paper will be available from our Hypatia entries, at http://hypatia.dcs.qmw.ac.uk. It is also available at http://www.dcs.qmw.ac.uk/~si. We are currently engaged in further study of the proof theory of the $\lambda\Lambda_{\kappa}$-calculus; this includes setting up a proposition-as-types correspondence and a Gentzenization of the type theory. We are also investigating categorical models, specifically resourced-indexed Kripke models, of the $\lambda\Lambda_{\kappa}$-calculus. Samin Ishtiaq David Pym From cat-dist Fri Feb 27 00:13:53 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id WAA21918 for categories-list; Thu, 26 Feb 1998 22:18:33 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Davide.Sangiorgi@sophia.inria.fr Date: Thu, 26 Feb 1998 16:59:23 +0100 (MET) Message-Id: <199802261559.QAA07833@laser.inria.fr> To: THEORYNT@LISTSERV.NODAK.EDU, concurrency@cwi.nl, categories@mta.ca, logic@CS.Cornell.EDU, types@cs.indiana.edu CC: Robert.De_Simone@sophia.inria.fr Subject: categories: CONCUR98: final CFP (EXTENDED deadline) Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: [Apologies if you receive multiple copies] !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Please note: -- extended deadline -- (very likely) The auditorium of Nice Museum of Modern and Contemporary Art as venue !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Last Call for Papers CONCUR'98 9th International Conference on Concurrency Theory Nice, France, September 8-11, 1998 Important dates ~~~~~~~~~~~~~~~ Paper submissions: March 18, 1998 (EXTENDED deadline) Notifications: May 8, 1998 Final versions: June 10, 1998. Venue and local arrangements ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Nice is ideally located on the French Riviera. September is still very pleasant, while less crowded than the high season. Nice's international airport is well-connected to all major european and non-european cities. Most likely the conference will be held at the auditorium of Nice Museum of Modern and Contemporary Art, which is conveniently located in the heart of Nice, between the city center and the old town, and 20 minutes walk to the beach. The Museum is next to the Hotel Novotel, where satellite workshops and registration will be held. CONCUR 98: Purpose and Scope ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The purpose of the CONCUR conferences is to bring together researchers, developers, and students in order to advance the theory of concurrency, and promote its applications. Interest in this topic is continuously growing, as a consequence of the importance of concurrent systems and their applications, and of the scientific relevance of their foundations. The scope of CONCUR'98 covers all areas of semantics, logics, and verification techniques for concurrent systems. A list of specific topics includes (but is not limited to) concurrency related aspects of models of computation and semantic domains, process algebras, Petri nets, event structures, real-time systems, hybrid systems, decidability, model-checking, verification techniques, refinement techniques, term and graph rewriting, distributed programming, logic constraint programming, object-oriented programming, typing systems and algorithms, case studies, tools and environments for programming and verification. Submissions: ~~~~~~~~~~~~~ Submissions should consist of a 100-200 word ASCII abstract and summary (up to 15 pages, typeset 12 points; about 7000 words, excluding bibliography and figures). Simultaneous submissions to other conferences or journals are not allowed. Electronic submissions in PostScript(tm) are strongly encouraged; instructions can be found at the URL , or can be obtained by sending an email with subject "submission information" to c98-subm@sophia.inria.fr. If surface mail is used, then five (5) copies of the paper should be sent to the following address: Concur'98, INRIA Sophia-Antipolis, BP 93, F-06902 Sophia-Antipolis Cedex, France. Program Committee ~~~~~~~~~~~~~~~~~~~ M. Abadi (Digital,Systems Research Center) A. Asperti (University of Bologna) J. Bradfield (University of Edinburgh) E. Clarke (Carnegie Mellon University) R. de Simone (INRIA Sophia-Antipolis, co-chair) J. Esparza (Technische Universitat Munchen) P. Gastin (University of Paris 7) R. van Glabbeek (Stanford University) G. Gonthier (INRIA Rocquencourt) M. Hennessy (Sussex University) O. Maler (Verimag Grenoble) F. Moller (Uppsala University) U. Montanari (University of Pisa) M. Mukund (SMI Madras) M. Nielsen (University of Aarhus) P. Panangaden (Mc Gill University) J. Parrow (Royal Institute of Technology, Stockholm) A. Rensink (University of Hildesheim) D. Sangiorgi (INRIA Sophia-Antipolis, co-chair) C. Talcott (Stanford University) J. Winkowski (Polish Academy of Sciences) Invited Speakers and Tutorials: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (in square brackets, the topic of the talk) Invited Speakers: T. Henzinger (University of California at Berkeley, USA) [Hybrid systems]; U. Herzog (Erlangen, Germany) [Process algebra for performance evaluation]; J. Rutten (CWI, Netherlands) [Coalgebraic models of computation]; J.-B. Stefani (CNET, France Telecom) [Open distributed systems]; M. Vardi (Rice University, USA) [Branching and linear time temporal logics]. Invited Tutorials : G. Berry (CMA Ecole des Mines, France) [Synchronous reactive programming and Esterel]; J.F. Groote (CWI, Netherlands) [Theorem provers in concurrency]; B. Pierce (Indiana U., USA) [Types in concurrency]. Financial Support ~~~~~~~~~~~~~~~~~~ We wish to thank the following companies and organisations for financial support: CNET France Telecom, Dassault Aviation, Simulog, CMA-Ecole des Mines, INRIA. Satellite events ~~~~~~~~~~~~~~~~~ COTIC'98: 2nd international workshop on Concurrent Constraint Programming for Time Critical Applications EXPRESS'98: 5th international workshop on Expressiveness in Concurrency HLCL'98: 3rd international workshop on High-Level Concurrent Languages PAPM'98: 6th international workshop on Process Algebra and Performance Modeling CONFER W.G.: 4th workshop of the CONFER (Concurrency and Functions: Evaluation and Reduction) working group. Publications ~~~~~~~~~~~~ The proceedings will be published by Springer-Verlag in the LNCS series. A special issue of Theoretical Computer Science is planned. Steering Committee ~~~~~~~~~~~~~~~~~~ The Steering Committee of CONCUR is composed of Jos Baeten (chair, Eindhoven), Eike Best (Oldenburg), Kim Larsen (Aalborg), Ugo Montanari (Pisa), Scott Smolka (Stony Brook) and Pierre Wolper (Liege). Organizing Committee ~~~~~~~~~~~~~~~~~~~~~ The Organizing Committee of CONCUR 98 is composed of Amar Bouali, Gerard Boudol, Ilaria Castellani, Robert de Simone, Catherine Juncker, Francoise Martin-Trucas, Davide Sangiorgi, and Dany Sergeant. ============================== For further information, check URL , or mail to concur98@sophia.inria.fr. From cat-dist Fri Feb 27 18:47:18 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA11261 for categories-list; Fri, 27 Feb 1998 16:11:53 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 27 Feb 1998 09:33:00 -0500 From: rblute@mathstat.uottawa.ca (Richard Blute) Message-Id: <9802271433.AA22493@castor> To: categories@mta.ca Subject: categories: Paper available Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The following paper is available by anonymous ftp at triples.math.mcgill.ca in the directory pub/blute as nuclear.ps.gz. It is also on Prakash Panangaden's homepage at www-acaps.cs.mcgill.ca. Feel free to contact me if there are any problems. Cheers, Rick Blute Nuclear and Trace Ideals in Tensored *-Categories ================================================= Samson Abramsky Richard Blute Department of Computer Science Department of Mathematics University of Edinburgh and Statistics Edinburgh, Scotland University of Ottawa Ottawa, Ontario, Canada Prakash Panangaden Department of Computer Science McGill University Montreal, Quebec, Canada Presented to Mike Barr on the occasion of his 60th birthday. Abstract ======== We generalize the notion of nuclear maps from functional analysis by defining nuclear ideals in tensored *-categories. The motivation for this study came from attempts to generalize the structure of the category of relations to handle what might be called ``probabilistic relations''. The compact closed structure associated with the category of relations does not generalize directly, instead one obtains nuclear ideals. Most tensored *-categories have a large class of morphisms which behave as if they were part of a compact closed category, i.e. they allow one to transfer variables between the domain and the codomain. We introduce the notion of nuclear ideals to analyze these classes of morphisms. In compact closed categories, we see that all morphisms are nuclear, and in the category of Hilbert spaces, the nuclear morphisms are the Hilbert-Schmidt maps. We also introduce two new examples of tensored *-categories, in which integration plays the role of composition. In the first, morphisms are a special class of distributions, which we call tame distributions. We also introduce a category of probabilistic relations which was the original motivating example. Finally, we extend the recent work of Joyal, Street and Verity on traced monoidal categories to this setting by introducing the notion of a trace ideal. For a given symmetric monoidal category, it is not generally the case that arbitrary endomorphisms can be assigned a trace. However, we can find ideals in the category on which a trace can be defined satisfying equations analogous to those of Joyal, Street and Verity. We establish a close correspondence between nuclear ideals and trace ideals in a tensored *-category, suggested by the correspondence between Hilbert-Schmidt operators and trace operators on a Hilbert space. When we apply our notion of trace ideal to the category of Hilbert spaces, we obtain the usual trace of an endomorphism in the trace class. From cat-dist Sat Feb 28 18:14:18 1998 Received: (from Majordom@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id PAA27745 for categories-list; Sat, 28 Feb 1998 15:54:14 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-SMTP-Posting-Origin: Math.McGill.CA (Gauss.Math.McGill.CA [132.206.150.3]) Date: Sat, 28 Feb 1998 11:41:14 -0500 (EST) From: Robert Seely To: Categories List , Types List Cc: Robin Cockett , Rick Blute Subject: categories: Paper on Feedback announced Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The following paper is available on RAG Seely's WWW home page at or directly by ftp at or Comments are most welcome; please send them to any of the authors. Any problems in obtaining the paper should be sent to rags@math.mcgill.ca. Feedback for linearly distributive categories: traces and fixpoints by R.F. Blute J.R.B. Cockett R.A.G. Seely ABSTRACT In the present paper, we develop the notion of a trace operator on a linearly distributive category, which amounts to essentially working within a subcategory (the "core") which has the same sort of "type degeneracy" as a compact closed category. We also explore the possibility that an object may have several trace structures, introducing a notion of compatibility in this case. We show that if we restrict to compatible classes of trace operators, an object may have at most one trace structure (for a given tensor structure). We give a linearly distributive version of the "geometry of interaction" construction, and verify that we obtain a linearly distributive category in which traces become canonical. We explore the relationship between our notions of trace and fixpoint operators, and show that an object admits a fixpoint combinator precisely when it admits a trace and is a cocommutative comonoid. This generalises an observation of Hyland and Hasegawa. This paper is presented to Bill Lawvere on the occasion of his 60th birthday. =================================== RAG Seely [ NB - please use the "generic" email address above and not machine specific e-addresses like "rags@triples.math.mcgill.ca" ] ===================================