Date: Thu, 2 Feb 1995 04:00:34 -0400 (AST) Subject: Algebraic structures for Eilenberg-Moore algebras Date: Wed, 01 Feb 1995 11:51:57 +0000 From: Andrea Schalk I'm looking for some pointer to literature where I can find the following (or a similar) Theorem: Let $(T,\eta,\mu)$ be a monad. Assume we have an algebraic structure such that every free algebra for that monad carries one of those algebraic structures and such that all morphisms of the form $Tf$ and all $\mu_C$ preserve it. Then all Eilenberg-Moore algebras carry such a structure and all morphisms between them preserve it. Thanks Andrea Schalk University of Cambridge Computer Lab Andrea.Schalk@cl.cam.ac.uk Date: Thu, 2 Feb 1995 04:02:08 -0400 (AST) Subject: Annonce Date: Wed, 1 Feb 95 16:50:02 +0100 From: Monique Mathieu JOURNEES D'ETUDE SUR LES ESQUISSES (Deuxieme annonce) organisees par P.Damphousse (Lab. math. Tours) R. Guitart (Eq.Theo. Geom., Paris 7) C. Lair (Eq. Cat. et Structures, Paris 7) UNIVERSITE PARIS 7 2 place Jussieu Paris 75005 Lundi 6 fevrier et mardi 7 fevrier 1995 9h-12h40 & 14h30-18h10 (salle 517, tours 55-56) Lundi 6 fevrier 9h : C. LAIR, Presentations diagrammatiques des theories : esquisses, trames et patchworks ... 10h20 : L. COPPEY, Esquisses et types, I. 11h40 : R. GUITART, P-esquisses. 14h30 : J. ROSICKY, Finitary and geometric sketches. 15h50 : C. LAIR, Proprietes generales des categories esquissables : diagrammes localement libres et permanence de formes. 17h10 : R. GUITART, Construction effective des diagrammes localement libres. Mardi 7 fevrier 9h : L. COPPEY, Esquisses et types, II. 10h20 : J. ROSICKY, Sketches and accessible categories. 11h40 : C. LAIR, Caracterisations intrinseques des categories esquissables : catgories modelables et catgories analysables. 14h30 : M. MATHIEU, Esquissabilite et monadicite. 15h50 : C. LAIR, Proprietes particulieres de certaines categories esquissables : exemples de traduction syntaxe-semantique et autres phenomenes de traduction. Date: Thu, 2 Feb 1995 22:59:55 -0400 (AST) Subject: Re: Algebraic structures for Eilenberg-Moore algebras Date: Thu, 2 Feb 95 08:39:39 EST From: Michael Barr - - Date: Wed, 01 Feb 1995 11:51:57 +0000 - From: Andrea Schalk - - - I'm looking for some pointer to literature where I can find the - following (or a similar) Theorem: - - Let $(T,\eta,\mu)$ be a monad. Assume we have an algebraic structure - such that every free algebra for that monad carries one of those - algebraic structures and such that all morphisms of the form $Tf$ - and all $\mu_C$ preserve it. Then all Eilenberg-Moore algebras carry - such a structure and all morphisms between them preserve it. - - Thanks - - Andrea Schalk - University of Cambridge - Computer Lab - - Andrea.Schalk@cl.cam.ac.uk - - I don't know of an explicit reference, but things of this sort are certainly familiar. Look, for example, at the proof in TTT that toposes are cartesian closed. For that matter, the proof that a slice of a topos is a topos uses the same idea. Michael Barr Date: Thu, 2 Feb 1995 23:03:30 -0400 (AST) Subject: re Algebraic structures for Eilenberg-Moore algebras Date: Thu, 02 Feb 1995 11:27:38 -0500 (EST) From: MTHISBEL@ubvms.cc.buffalo.edu ''From: Andrea Schalk I'm looking for some pointer to literature where I can find the following (or a similar) Theorem: Let $(T,\eta,\mu)$ be a monad. Assume we have an algebraic structure such that every free algebra for that monad carries one of those algebraic structures and such that all morphisms of the form $Tf$ and all $\mu_C$ preserve it. Then all Eilenberg-Moore algebras carry such a structure and all morphisms between them preserve it. Thanks'' I don't know where to look for such a theorem but would be more optimistic if I knew what 'carries' means. Harvey Friedman published something of this tendency about 1977, I think with semantic hypothesis and syntactic conclusion. John Isbell Date: Thu, 2 Feb 1995 23:08:33 -0400 (AST) Subject: Chair in Theoretical Computer Science at The University of Edinburgh Date: Thu, 2 Feb 1995 19:39:22 +0000 From: Gordon Plotkin The University of Edinburgh Chair in Theoretical Computer Science The University invites applications for a newly established Chair in Theoretical Computer Science, to be held within the Department of Computer Science. We seek a candidate who will further develop the strengths of the Department and its Laboratory for Foundations of Computer Science (LFCS). In addition to outstanding strength in research and scholarship, the successful candidate should provide leadership and inspiration for fundamental research, encourage the integration of his/her own research with that of others, and play an active role in teaching and departmental administration. The appointment is full-time, the salary will be within the normal professorial salary range and the person appointed will be required to retire at the end of the academic year in which he/she reaches the age of 65. Application Procedure Letters of application should include a curriculum vitae, and the names and addresses of 3 referees. Please include fax numbers for referees if possible. Applications should be addressed to the Secretary to the University, University of Edinburgh, and sent, to arrive not later than 31st March 1995, by post (1 Roxburgh Street, Edinburgh, EH8 9TB, Scotland, UK), or fax +44 (0)131 650 6509. The taking up of references is selective and does not imply a decision that the applicant will be placed on the final short-list for interview. Further particulars may be obtained from our WWW page, http://www.dcs.ed.ac.uk or from the Head of Department, Prof Roland N. Ibbett Department of Computer Science tel: +44 (0)131 650 5119 e-mail: hod@dcs.ed.ac.uk NOTE: This advertisement does not constitute a contract of employment and does not in any way override the terms of any contract of employment which may be issued subsequently to the successful candidate. The University reserves the right to make an appointment from outwith those candidates who have submitted formal applications. Date: Sun, 5 Feb 1995 20:36:16 -0400 (AST) Subject: query of A. Schalk Date: Sat, 4 Feb 95 09:26:05 EST From: Ernie Manes February 3, 1995 To: Andrea Schalk, Andrea.Schalk@cl.cam.ac.uk From: Ernie Manes, manes@math.umass.edu Re: Your query yesterday on cat-dist The question you asked was solved in my 1967 thesis and appears as Exercise 9 on page 217 of my book on Algebraic Theories, Springer-Verlag GTM 28, 1976 where the reference to the thesis is also given. In effect, if T is your monad and C is the category of algebraic structures, you give yourself a functor J : F ---> C where F is the full subcategory of free T-algebras. This is because a typical homomorphism between free T-algebras has the form of a composition Tf followed by a mu. Your question then amounts to asking for a canonical extension of J to the category of all T-algebras. This construction, based on contractible coequalizers, is given in the references cited in the first paragraph. All the best, egm Date: Sun, 5 Feb 1995 20:38:22 -0400 (AST) Subject: Re: Algebraic structures for Eilenberg-Moore algebras Date: Fri, 3 Feb 1995 15:52:31 +0000 (GMT) From: Dusko Pavlovic According to categories: > > Date: Wed, 01 Feb 1995 11:51:57 +0000 > From: Andrea Schalk > > > I'm looking for some pointer to literature where I can find the > following (or a similar) Theorem: > > Let $(T,\eta,\mu)$ be a monad. Assume we have an algebraic structure > such that every free algebra for that monad carries one of those > algebraic structures and such that all morphisms of the form $Tf$ > and all $\mu_C$ preserve it. Then all Eilenberg-Moore algebras carry > such a structure and all morphisms between them preserve it. > Manes' book "Algebraic Theories" contains many propositions and exercises of this kind, relating monadic and equational presentations of algebraic theories. I think something of this kind should be there. Regards, -- Dusko Pavlovic Date: Sun, 5 Feb 1995 20:40:59 -0400 (AST) Subject: Re: Algebraic structures for Eilenberg-Moore algebras Date: Fri, 3 Feb 1995 16:44:33 +0000 (GMT) From: Dusko Pavlovic > > Let $(T,\eta,\mu)$ be a monad. Assume we have an algebraic structure > such that every free algebra for that monad carries one of those > algebraic structures and such that all morphisms of the form $Tf$ > and all $\mu_C$ preserve it. Then all Eilenberg-Moore algebras carry > such a structure and all morphisms between them preserve it. > PS On a second thought, the matter of monadic vs. equational presentation just complicates things here. If we begin by presenting this algebraic structure, carried by all free T-algebras, as another monad, say (S,\eta,\mu), the proof boils down to two diagrams. The assumption that each free T-algebra is an S-algebra means that there is a natural transformation s:ST->T: its components are the given S-algebras on TX; the assumption that each Tf preserves the structure is just the naturality of s. On the other hand, the assumption that \mu of T preserves it means that \mu s = s S\mu. Using this and the naturalities, one directly checks that if a:TX->X is a T-algebra, then SX --S\eta--> STX --s--> TX --a--> X must be an S-algebra --- clearly preserved by T-morphisms. All the best, -- Dusko Date: Sun, 5 Feb 1995 20:42:14 -0400 (AST) Subject: Workshop on Descent Theory Date: Fri, 3 Feb 95 16:19:05 +1100 From: Walter Tholen Dear Colleagues: This is to inform you that we recently received approval for a workshop on "Descent Theory", to be held September 17 - 23, 1995, at the Mathematical Research Institute in Oberwolfach, Germany. It will be a specialized meeting with the aim to bring together people actively working on different aspects of descent theory. Unfortunately we got only a small portion of the space at Oberwol- fach, which means that this workshop can host only about 25 participants. It will therefore be a very small venture, not at all intended to compete with the more general conferences on category theory to be held in July and August in Halifax and in Cambridge, respectively. Following the usual Oberwolfach procedure, the Institute will sent out invitations for the meeting soon. Regards, George Janelidze Ieke Moerdijk Walter Tholen. Date: Tue, 7 Feb 1995 01:52:59 -0400 (AST) Subject: Higher-dimensional algebra and TQFT Date: Sun, 5 Feb 95 19:53:07 PST From: john baez The paper "Higher-dimensional algebra and topological quantum field theory", by John Baez and James Dolan, is now available by anonymous ftp as the file baez/tqft.tex from math.ucr.edu It is in LaTeX, but to LaTeX it you also need the files auxdefs.sty and diagram.sty, which are also in the directory baez. Here's an abstract: The study of topological quantum field theories increasingly relies upon concepts from higher-dimensional algebra such as n-categories and n-vector spaces. We review progress towards a definition of n-category suited for this purpose, and outline a program in which n-dimensional TQFTs are to be described as n-category representations. First we describe a `suspension' operation on n-categories, and hypothesize that the k-fold suspension of a weak n-category stabilizes for k greater than or equal to n + 2. We give evidence for this hypothesis and describe its relation to stable homotopy theory. We then propose a description of n-dimensional unitary extended TQFTs as weak n-functors from the `free stable weak n-category with duals on one object' to the n-category of `n-Hilbert spaces'. We conclude by describing n-categorical generalizations of deformation quantization and the quantum double construction. Date: Tue, 7 Feb 1995 02:05:21 -0400 (AST) Subject: Kleisli category for multiple monads? Date: Mon, 6 Feb 1995 14:07:19 -0500 From: David Espinosa Is it possible to form the Kleisli category of several monads at once? I can imagine an indexed product of the individual Kleisli categories, but I lack the technical facility to describe it. In my thesis, I have a category with multiple monads, relating the different "levels" of a denotational semantics (environments, stores, etc). See http://www.cs.columbia.edu/~espinosa/ for more info. The monad laws follow easily from the Kleisli formulation; they say that the Kleisli category is actually a category. The monad morphism laws say that an arrow between monads is a functor between Kleisli categories. What I expect from a "multi-Kleisli" formulation is that Kleisli compositions associate (when possible). Specifically, given monads P and PQ (where Q is another functor) and arrows f : A -> PQB g : QB -> PQC h : C -> PQD we'd like (oPQ (oP f g) h) = (oP f (oPQ g h)) where oP and oPQ are the Kleisli compositions of the monads. I can postulate a category with this structure, but it would be nicer if it came from a general construction. David -------------------- p.s. Other formulations of associativity are: ;; bindT : TA * (A -> TB) -> TB f : A -> PQB g : QB -> PQC (bindP (bindPQ pqa f) g) = (bindPQ pqa (lambda (a) (bindP (f a) g))) ;; mapT : (A -> B) * TA -> TB ;; joinT : TTA -> TA ;; f : A -> PQB ;; g : QB -> PQC (joinP (mapP g (joinPQ (mapPQ f pqa)))) = (joinPQ (mapPQ (lambda (a) (joinP (mapP g (f a)))) pqa)) Can we rewrite this using join in a more natural way? Date: Fri, 10 Feb 1995 02:07:34 -0400 (AST) Subject: eye has not seen Date: Thu, 9 Feb 1995 09:51:17 +0500 From: James Stasheff Have anyone ever seen the odd numbered pages of Pareigis' Endomorphism bialgebras of diagrams... apparently its part of a book has the book ever appeared?? Date: Fri, 10 Feb 1995 02:10:04 -0400 (AST) Subject: The Tbilisi Symposium on Language, Logic and Computation Date: Thu, 09 Feb 95 18:23:42 +0000 From: tbilisi@cogsci.edinburgh.ac.uk First Call For Papers The Tbilisi Symposium on Language, Logic and Computation -------------------------------------------------------- Tbilisi, Republic of Georgia October 19-22, 1995 Host institution: Tbilisi State University Dedicated to Solomon Dodashvili In order to foster communication between researchers in the Republic of Georgia and the international research community, the Georgian Centre for Language and Speech, based at the Tbilisi State University, will host an international symposium on language, logic and computation in 19-22, October 1995. The Tbilisi Symposium is anticipated to be the first of a regular series. TOPICS OF INTEREST: The Tbilisi Symposium will welcome papers on current research in all aspects of language, logic and computation, including but not limited to: * natural language semantics/pragmatics * dynamic and modal logic * quantified extensions of modal systems and intermediate logics: semantical and computational aspects * information oriented logical frameworks: domain theory, linear logic, situation theory * natural language parsing and generation * machine translation and translation aids * statistics and language processing * automated deduction and logic programming * lambda and combinatory calculi * process algebra * category theory in computer science INVITED SPEAKERS: R. Cooper (Edinburgh) P. Gardenfors (Lund) A. Joshi (Philadelphia) H. Ono (Ishikawa) A. Preller (Montpelier) H. Uszkoreit (Saarbruecken) R. Wojcicki (Warszawa) PROGRAMME COMMITTEE: J. van Benthem (Amsterdam) J. Bergstra (Amsterdam) P.L. Curien (Paris) G. Erbach (Saarbruecken) L. Esakia (Tbilisi) T. Fernando (Stuttgart) H. Ganzinger (Saarbruecken) J. Ginzburg (Edinburgh) D. de Jongh (Amsterdam) E. Klein (Edinburgh) Z. Khasidashvili (Norwich) (Co-chair) E. Khmaladze (Tbilisi) J.-J. Levy (Rocquencourt) (Co-chair) A. Mikheev (Edinburgh) S. Peters (Stanford) K. Segerberg (Stockholm) E. Vallduvi (Edinburgh) PROCEEDINGS: The papers will be refereed and a selection will appear as a book published by the Center for the Study of Language and Information (CSLI), Stanford. SUBMISSION DETAILS: Papers not exceeding 10-pages should be submitted electronically or, if electronic submission is problematic, in hard copy. Electronic submissions should be in plain text, latex, or ready-to-print postscript. Papers submitted by postal mail should be accompanied by 3 additional copies. No fax submissions. Papers should be accompanied by a two-page abstract. The abstract should also include the full postal and e-mail address and fax/phone of the author (or a designated contact author in case of joint papers), as well as a specification of the topic area. These abstracts will be collated together and will be made available to all symposium participants. Papers should be submitted to: The Tbilisi Symposium E-mail: tbilisi@cogsci.ed.ac.uk Human Communication Research Centre Phone: +44 131 650 4667 University of Edinburgh Fax: +44 131 650 4587 2 Buccleuch Place Edinburgh, EH8 9LW Scotland, UK SCHEDULE: Authors must submit their 10-page papers by 31 May 1995. Notification of receipt will be mailed to the (contact) author. Authors will be notified of acceptance by 15 July 1995. The deadline for submission of final versions of the presented papers will be 31 October 1995. Papers will undergo review and a selection will be published in the proceedings. We expect the proceedings to appear in the first half of 1996. Final submission details will be sent along with the symposium materials. ORGANISING COMMITTEE: J. Ginzburg (Co-Chair) E. Vallduvi (Co-Chair) Human Communication Research Centre Centre for Cognitive Science University of Edinburgh University of Edinburgh 2 Buccleuch Place 2 Buccleuch Place Edinburgh EH8 9LW Edinburgh EH8 9LW Scotland Scotland ginzburg@cogsci.ed.ac.uk enric@cogsci.ed.ac.uk Phone: +44-131-650-4627 Phone: +44-131-650-4451 Fax: +44-131-650-4587 Fax: +44-131-650-4587 Z. Khasidashvili (Programme Co-Chair) J.-J. Levy (Programme Co-chair) School of Information Systems INRIA Rocquencourt, University of East Anglia Domaine de Voluceau, Norwich NR4 7TJ B.P. 105, 78153 Le Chesney Cedex England France zurab@sys.uea.ac.uk Jean-Jacques.Levy@inria.fr Phone: +44-1603-592607 Phone: +33 1 39 63 56 44 Fax: +44-1603-593344 Fax: +33 1 39 63 55 11. LOCAL ORGANISING COMMITTEE: Chair: T. Khurodze (Vice-rector, TSU) Vicechair: N. Chanishvili (Dept. of Modern Georgian, TSU); Secretaries: R. Asatiani (Inst. of Oriental Studies, GAS); T. Sukhiashvili (Inst. of Cybern., GAS). Georgian Academy of Sciences: M. Abashidze, R. Grigolia (Inst. of Cybern.); G. Tagviashvili (Inst. of Computational Math.); G. Chikoidze (Inst. of Control Systems); N. Amiridze (Inst. of Oriental Studies); T. Uturgaidze (Inst. of Linguistics); M. Bejanishvili (Inst. of Philosophy); Tbilisi State University: J. Antidze, T. Kutsia (Inst. of Applied Math.); L. Mchedlishvili, N. Ivanidze (Dept. of Logics); L. Chkhaidze (Inst. Comp. Science and Telecommunication); LOCATION: The Republic of Georgia offers many singular attractions. Tbilisi is a beautiful urban centre of Georgia, which is rich in architectural, historical, and natural attractions. Tbilisi is easily accessible by plane from many major European cities (e.g. several flights per week from Frankfurt, Istanbul, Koeln, Paris, Prague, Thessaloniki, Vienna). There are also direct flights to Tbilisi from Tel Aviv and Cairo. SOLOMON DODASHVILI: Solomon Dodashvili was a Professor at St. Petersburg University. He is the author of a well-known tutorial book of logic, published by St. Petersburg University in 1827. In 1995 Georgia will celebrate the 190th anniversary of his birth. An excursion will be organised to the Kakheti region, where Dodashvili was born. CONFERENCE INFORMATION: This announcement (ascii, dvi and postcript formats) is available via anonymous FTP from ftp.cogsci.ed.ac.uk in directory pub/tbilisi. Information about flight schedules to Tbilisi is also available. For further information contact the Edinburgh address above. Information on registration and accommodation will appear in future announcements Date: Fri, 10 Feb 1995 22:50:50 -0400 (AST) Subject: WoLLIC '95 - Recife, Brazil Date: Fri, 10 Feb 1995 09:23:41 GMT From: Ruy de Queiroz First Call for Contributions 2nd Workshop on Logic, Language, Information and Computation WoLLIC '95 July 26--28, 1995 Recife, Brazil The `2nd Workshop on Logic, Language, Information and Computation' (WoLLIC '95), will be held in Recife, on the northeastern coast of Brazil, from 26th to 28th July 1995. Contributions are invited in the form of two page (600 words) abstract in all areas related to logic, language, information and computation, including: pure logical systems, proof theory, model theory, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and AI, automated deduction, foundations of logic programming, logic and computation, and logic engineering. There will be a number of guest speakers, including (so far preliminarily confirmed): M. Abadi (Palo Alto), C. Alchourron (Buenos Aires), A. Avron (Tel Aviv), N. Belnap (Pittsburgh), J. van Benthem (Amsterdam), P. Freyd (Philadelphia), D. Gabbay (London), I. Hodkinson (London), P. Lincoln (Stanford), V. Pratt (Stanford). Submission: Two-page abstracts (preferably by e-mail to wollic95@di.ufpe.br) must be RECEIVED by JUNE 1ST, 1995 by the Chair of the Organising Committee. Authors will be notified of acceptance by July 1st, 1995. WoLLIC '95 is sponsored by the Interest Group in Pure and Applied Logics (IGPL) and The European Association for Logic, Language and Information (FoLLI). Abstracts from members of the IGPL will be published in the Bulletin of the IGPL (ISSN 0945-9103) as part of the meeting report. Selected contributed papers will be invited for submission to a special issue of the Bulletin. The location: Recife is the capital of the sun belt coast in the northeast of Brazil, just 8 degrees below Equator, bathed by 250+ days of sun/year (i.e. Caribbean-like climate). City population is around 2.5 million and the life style is quite relaxed. Recife is over 450 years old, has a number of interesting architectural samples of Portuguese colonial times (esp. XVII and XVIII centuries), and is neighbour to picturesque Olinda, whose architectural heritage is protected by UNESCO. Programme Chair: Prof P. A. S. Veloso, Departmento de Informatica, PUC-Rio, Rua Marques de Sao Vicente, 225, Rio de Janeiro, RJ 22453-900, Brazil, veloso@inf.puc-rio.br, tel: +55 21 529 9524, fax: +55 21 511 5645. Programme Committee: W. A. Carnielli (UNICAMP, Campinas), M. Costa (EMBRAPA, Brasilia), V. de Paiva (Cambridge, UK), R. de Queiroz (UFPE, Recife), A. Haeberer (PUC, Rio), T. Pequeno (UFC, Fortaleza), L. C. Pereira (PUC, Rio), A. M. Sette (UNICAMP, Campinas), P. Veloso (Chair, PUC, Rio). For further information, contact the Chair of Organising Committee: R. de Queiroz, Departamento de Informatica, Federal University of Pernambuco (UFPE) at Recife, P.O. Box 7851, Recife, PE 50732-970, Brazil, e-mail: wollic95@di.ufpe.br, tel: +55 81 271 8430, fax +55 81 271 4925. (Co-Chair: T. Pequeno, LIA, UFC, tarcisio@lia1.ufc.br, fax +55 85 223-1333) Date: Fri, 10 Feb 1995 22:52:54 -0400 (AST) Subject: actes de CAEN 94 Date: Fri, 10 Feb 1995 18:09:42 --100 From: Pierre Ageron (* This is to announce that the proceedings of the C.A.E.N. workshop, which was held in September 1994, will soon be available to everybody who is interested *) Les actes des journees CAEN 94 (Categories, Algebres, Esquisses, Neo-esquisses) seront disponibles en principe a la fin du mois de fevrier 1995. Ils comprennent des contributions originales, soigneusement relues et corrigees, des auteurs suivants : DEHORNOY, PORTER, DUVAL et REYNAUD, LAFONT, JOHNSTONE, DRECKMANN, VAN DE WIELE, GERNER et GUITART, GUITART, DAMPHOUSSE et GUITART, GORDON et POWER, SENECHAUD, LELLAHI, BOURN, AGERON, BURRONI et PENON, WEHRUNG, BROWN, MATHIEU, LAIR, RETORE, STELL. La plupart de ces articles sont en francais, les autres sont en anglais; ils totalisent 142 pages. Le volume d'actes sera envoye gratuitement a chaque personne qui en fait la demande, ceci dans la limite du tirage prevu (un seul exemplaire par personne ou bibliotheque). Il suffit pour cela de m'envoyer votre commande par la poste, en indiquant clairement l'adresse a laquelle il devra etre expedie. Les commandes faites par courrier electronique ne seront pas prises en compte. Les auteurs n'ont bien evidemment pas a passer commande. Pierre AGERON Departement de Mathematiques Universite de Caen 14032 CAEN Cedex FRANCE Date: Fri, 10 Feb 1995 22:56:53 -0400 (AST) Subject: The recent question of Andrea Schalk, and replies to it. Date: Fri, 10 Feb 95 18:21:27 +1100 From: Max Kelly The best answer was that of Ernie Manes. What is at stake is one very simple observation: if A is the category of algebras for a monad (perhaps in the context of enriched category theory) and F is the full subcategory given by the free algebras, then F is dense in A, and moreover this density may be "presented" by coequalizers. For the meaning of "density presentation", a notion due to Brian Day, see p.172 of my book "Basic Concepts of Enriched Category Theory", CUP 1982. Here it means that every algebra is a coequalizer of a pair of maps between free algebras, IN SUCH A WAY THAT this colimit is preserved by the representables A(f,-) where f is a free algebra; and this is very easy to see. Now Thm 5.30 of my book gives a very simple proof that the left Kan extension along J: F --> A of any functor T: F --> B exists, provided only that B has coequalizers. The observation of Dusko Pavlovic, that an elegant argument is to hand when B too is monadic, gives too SPECIAL a result. The others that have answered don't seem to have pointed out that the "canonical" extension of T they refer to IS indeed the left Kan extension. Max Kelly. Date: Wed, 15 Feb 1995 05:16:20 -0400 (AST) Subject: Summer School on Semantics and Logic of Computation Date: Tue, 14 Feb 1995 08:55:49 +0000 From: Andrew Pitts A Newton Institute Summer School SEMANTICS AND LOGICS OF COMPUTATION 25--29 September 1995 Newton Institute, Cambridge, UK in collaboration with the ESPRIT CLICS-II project Call for Registration The Summer School on Semantics and Logics of Computation is being held as part of a six-month research programme on Semantics of Computation at the Isaac Newton Institute for Mathematical Sciences, a new international research centre in Cambridge UK. The Summer School is sponsored by the CEC ESPRIT research project "Categorical Logic in Computer Science, II" (CLICS-II). The aim is to present a number of modern developments in semantics and logics of computation in a way that is accessible to graduate-level students. Registrations from postgraduate students will be given priority, but applications by interested academics and industrialists are also welcomed. The planned courses include: Samson Abramsky (Imperial) on "Semantics of interaction" Thierry Coquand (Chalmers) on "Computational content of classical logic" Martin Hofmann (Edinburgh) on "Dependent type theory: syntax, semantics, and applications" Martin Hyland (Cambridge) on "Game Semantics" Eugenio Moggi (Genova) on "Computational types and applications" Mogens Nielsen & Glynn Winskel (Aarhus) "Models for concurrency" Andrew Pitts (Cambridge) "Operationally-based theories for proving program properties" ORGANIZERS: For CLICS-II: Peter Dybjer (Chalmers) peterd@cs.chalmers.se For the NIMS Semantics of Andrew Pitts (Cambridge) Computation Programme: ap@cl.cam.ac.uk LOCATION: The workshop will take place in the Newton Institute's purpose-designed building, in a pleasant area in the west of Cambridge, about one mile from the centre of the City. Accommodation for participants will be provided next door to the Newton Institute in the study bedrooms of Girton College's Wolfson Court. The accommodation will be available from the evening of Sunday 24 September until the morning of Saturday 30 September. FEES: general rate: 400 pounds student rate: 250 pounds The fee covers registration, accommodation, meals (breakfast, lunch, supper, tea & coffee breaks), and lecture materials. REGISTRATION: There are only a limited number of places available on the Summer School. Intending participants are advised to apply for registration as soon as possible, and in no case later than 31 May 1995. To apply, please send your name and address (including e-mail or fax number, if available) to: Florence Leroy (SEM Summer School) Isaac Newton Institute 20 Clarkson Road Cambridge CB3 0EH Tel: +44 1223 335984 Fax: +44 1223 330508 Email: f.leroy@newton.cam.ac.uk IMPORTANT DATES: Deadline for registration 31 May 1995 Arrival date 24 September 1995 Scientific programme 25--29 September 1995 Departure date 30 September 1995 --------------------------------------------------------------------------- Date: Wed, 15 Feb 1995 05:17:50 -0400 (AST) Subject: LICS'95 Accepted Papers Date: Tue, 14 Feb 95 11:38 EST From: Amy Felty Day 1 ===== Program Logics -------------- Completeness of Kozen's Axiomatisation of the Propositional $\mu$-Calculus, Igor Walukiewicz Once and For All, Orna Bernholtz, Amir Pnueli Complete Proof Systems for First Order Interval Temporal Logic, Bruno Dutertre Finite Models I --------------- The Infinitary Logic of Sparse Random Graphs, James F. Lynch, Jerzy Tyszkiewicz Generalized Quantifiers and 0-1 Laws, Anuj Dawar, Erich Gr\"{a}del Relativized Logspace and Generalized Quantifiers over Finite Structures, Georg Gottlob First-order Queries on Finite Structures over the Reals, Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht Model Checking and Verification ------------------------------- Model-Checking of Causality Properties, Rajeev Alur, Doron Peled, Wojciech Penczek On the Complexity of Modular Model Checking, Moshe Y. Vardi Timing Behavior Analysis for Real-Time Systems, Farn Wang On the Verification Problem of Nonregular Properties for Nonregular Processes, Ahmed Bouajjani, Peter Habermehl, Rachid Echahed Day 2 ===== Theorem Proving and AI ---------------------- Uniform Proofs and Disjunctive Logic Programming, Gopalan Nadathur, Donald W. Loveland Structural Cut Elimination, Frank Pfenning Paramodulation without Duplication, Christopher Lynch Complexity of Normal Default Logic and Related Modes of Nonmonotonic Reasoning, V. Wiktor Marek, Anil Nerode, Jeffrey B. Remmel Concurrency I ------------- Control Structures, Alex Mifsud, Robin Milner, John Power Configuration Structures, R. J. Van Glabbeek, G. D. Plotkin A Typed Calculus of Synchronous Processes, Simon Gay, Rajagopal Nagarajan Modal $\mu$-Types for Processes, Marino Miculan, Fabio Gadducci Semantics I ----------- Games and Full Abstraction for the Lazy $\lambda$-Calculus, Samson Abramsky, Guy McCusker Games Semantics for Full Propositional Linear Logic, Fran\c{c}ois Lamarche A Fully Abstract Semantics for a Concurrent Functional Language with Monadic Types, Alan Jeffrey Day 3 ===== Lambda-Calculus and Types ------------------------- Equality Between Functionals in the Presence of Coproducts, Daniel J. Dougherty, Ramesh Subrahmanyam A Logic of Subtyping, Giuseppe Longo, Kathleen Milsted, Sergei Soloviev Normalization and Extensionality, Adolfo Piperno New Notions of Reduction and Non-Semantic Proofs of $\beta$-Strong Normalization in Typed $\lambda$-Calculi, A. J. Kfoury, J. B. Wells Finite Models II ---------------- Finitely Monotone Properties, Alexei P. Stolboushkin Tree Canonization and Transitive Closure, Kousha Etessami, Neil Immerman Ptime Canonization for Two Variables with Counting, Martin Otto When Do Fixed Point Logics Capture Complexity Classes?, Anil Seth Unification and Rewriting ------------------------- Higher-Order Unification via Explicit Substitutions, Gilles Dowek, Th\'{e}r\`{e}se Hardin, Claude Kirchner Sequentiality, Second Order Monadic Logic and Tree Automata, Hubert Comon Orderings, AC-Theories and Symbolic Constraint Solving, Hubert Comon, Robert Nieuwenhuis, Albert Rubio Day 4 ===== Model Checking II ----------------- Efficient On-the-Fly Model Checking for $CTL^{*}$, Girish Bhat, Rance Cleaveland, Orna Grumberg Partial Model Checking, Henrik Reif Andersen Hardware Verification via Boolean Logic Programming, Enrico Tronci Concurrency II -------------- Compositionality via Cut-Elimination: Hennessy-Milner Logic for an Arbitrary GSOS, Alex K. Simpson Compositional Testing Preorders for Probabilistic Processes, Bengt Jonsson, Wang Yi Semantics II ------------ The Stone Gamut: A Coordinatization of Mathematics, Vaughan R. Pratt Logically Presented Domains, Erik Palmgren, Viggo Stoltenberg-Hansen Domain Theory in Stochastic Processes, Abbas Edalat Linear Logic ------------ Decision Problems for Second Order Linear Logic, Patrick Lincoln, Andre Scedrov, Natarajan Shankar The Complexity of Neutrals in Linear Logic, Max I. Kanovich Decidability of Linear Affine Logic, Alexei P. Kopylov Date: Sat, 18 Feb 1995 21:23:48 -0400 (AST) Subject: Faculty positions of potential interest to <> readers Date: Sat, 18 Feb 1995 17:10:20 -0800 From: David B. Benson Faculty Positions in Computer Science School of Electrical Engineering and Computer Science Washington State University The School of Electrical Engineering and Computer Science solicits applications for a permanent computer science faculty position at the Assistant Professor level. Responsibilities include initiation and supervision of research programs and instruction at undergraduate and graduate levels. Applicants should have an earned PhD degree in Computer Science or in a closely related field by Fall 1995. We seek outstanding and accomplished candidates in specific areas of computer science which include computer systems, software engineering, database systems, networks and distributed systems. Screening of applications will begin on March 15 and continue until the position is filled. Position starts on August 15, 1995. The School of Electrical Engineering and Computer Science solicits applications for a permanent computer science faculty position at Associate or Full Professor level. Responsibilities include initiation and supervision of research programs and instruction at undergraduate and graduate levels. Applicants should have an earned PhD degree with proven records of accomplishment in their fields as evidenced by sponsored research programs and publications. We seek outstanding and accomplished candidates in specific areas of computer science which include software engineering, specification and verification, operating systems, database systems, and other related software areas. Screening of applications will begin on December 15 and continue until the position is filled. Position start on August 15, 1995. ----------------- Washington State University has offered the Ph.D. in computer science since 1970, and also offers B.S. and M.S. degrees. The School of EECS has over forty faculty (approximately fifteen with primary interests in computer science and engineering), sixty computer science graduate students, and active research groups devoted to parallel and distributed processing, imaging (computer graphics, visualization, image processing, and vision), artificial intelligence, neural networks, and other areas. Computing facilities in the School of EECS include PCs, graphics workstations, and servers, all with Internet access. WSU has about 17,000 students and is located in Pullman, a quiet university town in the southeast corner of the state (approximately 75 miles south of Spokane). Nearby are some of the nation's most pristine and uncrowded places for outdoor recreation. The Pullman school system is widely acknowledged to be one of the very finest in the Pacific Northwest. ! Applicants should send a cover letter, a curriculum vita, and the names and ! addresses of three references qualified to comment on their research and ! teaching qualifications to ! ! Chair, Computer Science Search Committee ! School of Electrical Engineering and Computer Science ! Washington State University ! Pullman, WA 99164-2752 WSU is an EO/AA educator and employer. Protected group members are encouraged to apply. Date: Wed, 22 Feb 1995 03:55:04 -0400 (AST) Subject: course on categories available Date: Tue, 21 Feb 1995 15:46:42 +0100 From: Jaap van Oosten I wrote a first course in category theory which I think more or less contains what's presumed knowledge in not too specialized papers and thesises (in computer science). It's 75 pages. The synopsis is: 1. Categories and functors. Definitions and examples. Duality principle. 2. Natural transformations. Exponents in Cat. Yoneda lemma. Equivalence of categories; Set^{op} equivalent to Complete Atomic Boolean Algebras. 3. Limits and Colimits. Functors preserving (reflecting) them. (Finitely) complete categories. Limits by products and equalizers. 4. A little piece of categorical logic. Regular categories, regular epi-mono factorization, subobjects. Interpretation of coherent logic in regular categories. Expressing categorical facts in the logic. Example of \Omega -valued sets for a frame \Omega. 5. Adjunctions. Examples. (Co)limits as adjoints. Adjoints preserve (co)limits. Adjoint functor theorem. 6. Monads and Algebras. Examples. Eilenberg Moore and Kleisli as terminal and initial adjunctions inducing a monad. Groups monadic over Set. Lift and Powerset monads and their algebras. Forgetful functor from T-Alg creates limits. 7. Cartesian closed categories and the \lambda-calculus. Examples of ccc's. Parameter theorem. Typed \lambda calculus and its interpretation in ccc's. Ccc's with natural numbers object: all primitive recursive functions are representable The notes are available by anonymous ftp via: ftp ftp.daimi.aau.dk cd pub/BRICS/LS/95/1 get BRICS-LS-95-1.ps.gz Jaap van Oosten Date: Thu, 23 Feb 1995 23:57:19 -0400 (AST) Subject: FinLim et FinProd ? Date: Thu, 23 Feb 95 16:18:35 +0100 From: Monique Mathieu Lors des Journees d'Etude sur les Esquisses du 6 et 7 fevrier, organisees a Paris 7, j'ai ete sollicitee pour parler sur le theme " esquissabilite et monadicite ". J'ai relu differents textes a cette occasion et j'ai notamment trouve une construction tres naturelle de l'esquisse des categories a limites choisies, construction qui demontre de plus la monadicite de cette categorie sur Cat. Recemment, on m'a montre le texte de Atish Bagchi et Charles Wells : " Graph-based Logic and Sketches I : The General Framework ". Je trouve ce texte fort bien ecrit mais complique, notamment la construction des esquisses de categories a produits ou limites choisis (FinProd et FinLim), sans comprendre la raison de cette complication. Quelqu'un peut-il m'expliquer l'interet (cache) de cette complication ? Je peux, bien sur, envoyer a quiconque me le demandera mes references, voire un resume, en anglais si necessaire, de la construction que j'annonce. Cordialement. Monique Mathieu. Date: Sun, 26 Feb 1995 02:03:41 -0400 (AST) Subject: Appointment Date: Fri, 24 Feb 1995 10:37:04 GMT From: ajp@dcs.ed.ac.uk Dear Colleagues, It gives me great pleasure to announce that Edmund Robinson has accepted a full professorship in the Computer Science Department of the Queen Mary and Westfield College of the University of London. It is one of the best Computer Science departments in Britain. Peter Landin is there, as is David Pym, and I believe Samson Abramsky received his doctorate there. With best wishes, John Power. Date: Sun, 26 Feb 1995 02:06:28 -0400 (AST) Subject: Research Fellowships at QMW Date: Fri, 24 Feb 1995 13:54:28 +0100 (MET) From: Edmund Robinson Please bring these research fellowships to the notice of anyone you think might be interested. all best wishes Edmund Robinson -------------------------------------------------------------------- Department of Computer Science Queen Mary & Westfield College University of London ADVANCED / SENIOR RESEARCH FELLOWSHIPS As an important part of our strategy to accelerate research activity in this highly-rated research department we wish to appoint a small number of full-time Research Fellows in Computer Science. The fellowships will be of one to two years duration and are aimed at experienced researchers who would benefit from collaborating with staff at QMW in a lively and well resourced research setting. The department (rated 4A in the last research selectivity exercise) has strong well resourced research groups in several mainstream areas of computer science including; artificial intelligence; computer graphics and virtual reality; distributed and parallel systems; human computer interaction, programming and the theory of computation. Applicants for an Advanced Fellowship (Ref: 95034) should have a PhD in a relevant area of computer science together with a minimum of two years research experience and sound publication record providing evidence of potential to lead research. Salary will be in the range 16,075 - 23,087 pounds. Applicants for a Senior Research Fellowship (Ref: 95035) must have a minimum of five years research experience since obtaining their PhD in a relevant area of computer science together with an excellent publication record providing evidence of a significant contribution to their chosen area of computer science and proven ability to lead research. Salary will be in the range 26511 - 32665 pounds. For informal discussions contact Mel Slater (mel@dcs.qmw.ac.uk) (0171 975 52..) further information about the department can be found on World Wide Web: http://www.dcs.qmw.ac.uk/ For an application form and further details, please telephone our 24 hour Recruitment Line on 0171 975 5171, quoting the relevant Reference Number. Completed applications forms should be returned by 14th March 1995 to the Recruitment Coordinator, Personnel Office, Queen Mary and Westfield College, Mile End Road, London E1 4NS. ------------------------------------------------------------- This announcement is also available on World Wide Web: http://www.dcs.qmw.ac.uk/~mel/Admin/fellowad.html Date: Tue, 28 Feb 1995 00:16:28 -0400 (AST) Subject: APCS questionnaire form Date: Sun, 26 Feb 95 10:47 GMT From: Dr. P.T. Johnstone The following is the (slightly amended) text of an e-mail message I have just sent to Paula Sonneveld at Kluwer Academic Publishers. It should be self-explanatory. If you agree with me about the questionnaire form, please send a message to Ms Sonneveld (paula.sonneveld@wkap.nl) saying so---it is only by concerted action that we can check the spread of this bureaucratic nonsense. Peter Johnstone ___________________________________________________________________ Dear Ms Sonneveld, I have just sent you a report on paper no. (deleted) by (name deleted), which you asked me to referee for the journal `Applied Categorical Structures'. Having refereed several papers for this journal, I am becoming increasingly irritated by the questionnaire form which you send out with every paper. Several of the questions on this form are invariably irrelevant to mathematical papers, and those that do have some relevance are almost always impossible to answer with a straight `yes' or `no'---the only sensible answer is `read my detailed report'. So it seems to me that the questionnaire is a complete waste of time and paper. I therefore wish to inform you that, although I remain entirely willing to referee papers for `Applied Categorical Structures', I shall in future ignore any papers which you send to me accompanied by this questionnaire. I further intend to publicize this decision via the `Categories' electronic mailing list, and to urge other category-theorists who have refereed for APCS and who agree with me about the uselessness of this form to take the same action. Yours sincerely, Peter Johnstone