May 2004 - Categories - categories.org.au

\phi for the golden ratio?
by Oswald Wyler 06 Jun '04

06 Jun '04

In seventh or eighth grade -- a long time ago -- , I learned the name "goldener Schnitt" (golden ratio, ratio aurea) for the positive solution of the equation x^2 = x + 1. Recently, I read an article, I forgot where, discussing this number and using \phi as the "accepted symbol" for it. The old name was never mentioned. So far, I have only met three real or complex numbers with universally accepted one-letter symbols: \pi, e, i. Have I missed something? Oswald Wyler

4 3

Announcing two abstracts
by Fred E.J. Linton 01 Jun '04

01 Jun '04

An abstract of my proposed talk for next month's CT04 at UBC Vancouver has just been put up at http://fej.math.wes.home.att.net/CT04-Abstract.htm . My talks at Union College, Bangalore, and Calcutta last November, December, and January, respectively, are abstracted in the item http://b.mikolajewska.home.att.net/text/SIPRfejAbstrct.htm , which also provides links to two browser-optimized versions (one for Netscape, one for MSIE; I hope that other browsers will find that at least one of these renders acceptably) of a uniform write-up of what I had to say at those events. Comments, suggestions, errata, broken HTML? Please call these all to my attention. Thanks. -- F.E.J. Linton (Math/CS, Wesleyan U., Middletown, CT 06459 USA)

1 0

comparing cotriples via an adjoint pair
by Gaunce Lewis 31 May '04

31 May '04

I have encountered a situation in which I have two categories C, D which are related by a pair of adjoint functors L from C to D and R from D to C. Also, there is a cotriple S on C and a cotriple T on D. Finally, there is a natural isomorphism f from RT to SR. It seems that if a couple of diagrams relating f to the structure maps of the cotriples commute, then there is an induced adjoint pair relating the two coalgebra categories. Is this, or something similar to it, in the literature in some easily referenced place? Thanks, Gaunce

6 5

Call for Participation: Workshop on Quantum Programming Languages
by Peter Selinger 30 May '04

30 May '04

CALL FOR PARTICIPATION 2nd International Workshop on Quantum Programming Languages (QPL2004) July 12-13, 2004, Turku, Finland Affiliated with LICS 2004 http://quasar.mathstat.uottawa.ca/~selinger/qpl2004/ * * * Registration for this workshop is now available, please see below for registration information and a list of talks. OVERVIEW: The goal of this workshop is to bring together researchers working on mathematical formalisms and programming languages for quantum computing. In the last few years, there has been a growing interest in logical tools, languages, and semantical methods for analyzing quantum computation. These foundational approaches complement the more mainstream research in quantum computation which emphasizes algorithms and complexity theory. Possible topics include the syntax and semantics of quantum programming languages, new paradigms for quantum programming, specification of quantum algorithms, higher-order quantum computation, quantum data types, reversible computation, axiomatic approaches to quantum computation, concurrent and distributed quantum computation, compilation of quantum programs, semantical methods in quantum information theory, and categorical models for quantum computation. The first workshop in this series was held June 15-16, 2003, in Ottawa, Canada. REGISTRATION: Registration and local arrangements will be handled through the LICS 2004 main conference (http://www.dcs.ed.ac.uk/home/als/lics/lics04/) There will be a small fee for attending the workshop, which will cover lunch, coffee, and the informal proceedings. INVITED SPEAKER: * Richard Jozsa (Bristol): "On the structure of quantum algorithms and the role of classical mathematics" CONTRIBUTED TALKS: * Samson Abramsky, Ross Duncan: "A categorical quantum logic" * Pablo Arrighi, Gilles Dowek: "Operational semantics for formal tensorial calculus" * Alexandru Baltag, Sonja Smets: "A dynamic logic for quantum programming" * Bob Coecke: "Quantum, concretely, abstractly" * Ellie D'Hondt, Prakash Panangaden: "Quantum weakest preconditions" * Simon Gay, Rajagopal Nagarajan: "Communicating quantum processes" * Philippe Jorrand, Marie Lalire: "A process algebraic approach to concurrent and distributed quantum computation: operational semantics" * Peter Selinger: "Towards a semantics for higher-order quantum computation" * K. M. Svore, A. W. Cross, A. V. Aho, I. L. Chuang, S. A. Edwards, I. L. Markov: "Toward a software architecture for quantum computing design tools" * Benoit Valiron: "Quantum typing" * Paolo Zuliani: "Non-deterministic quantum programming" PROGRAM COMMITTEE: Samson Abramsky (Oxford) Prakash Panangaden (McGill) Peter Selinger (Ottawa) CONTACT INFORMATION: Organizer: Peter Selinger Department of Mathematics and Statistics University of Ottawa, Canada Email: selinger(a)mathstat.uottawa.ca CONFERENCE WEBSITE: http://quasar.mathstat.uottawa.ca/~selinger/qpl2004/ (revised May 29, 2004)

1 0

CT04 Abstracts and Early Registration
by John MacDonald 27 May '04

27 May '04

FIFTH ANNOUNCEMENT INTERNATIONAL CATEGORY THEORY CONFERENCE (CT04) July 18-24, 2004 University of British Columbia Vancouver, Canada This conference will be held on the University of British Columbia campus. It will begin with a reception at 6pm on Sunday July 18, 2004, and will end at 1pm on Saturday July 24, 2004. All those interested in category theory and its applications are welcome. Information about deadlines for abstracts, registration and accommodation may be found at the end of this letter as well as on the conference website http://www.pims.math.ca/science/2004/CT04 If you think that you will attend or may attend, and have not previously made any indication of this to the organizer, then please send a note to johnm(a)math.ubc.ca with the words "will attend" or "may attend", as appropriate. The issue involved here is whether the PIMS new lecture room can be used for the talks or whether something bigger will have to be booked. Some important deadlines are as follows: Abstracts - May 31, 2004. If you would like to give a talk at the conference, then please send in a short abstract of length about half a page but not longer than one page. Please submit this on the form from the conference website http://www.pims.math.ca/science/2004/CT04/abstracts.html Due to the potentially large number of submissions it may not be possible to reserve a place on the program for all those who submit an abstract. Registration Deposit or Early Registration payment - May 31, 2004 Please see the website http://www.pims.math.ca/science/2004/CT04/registration.html It is possible to make payment by bank transfer in addition to the option of payment by cheque. Details of the address and account number can be supplied on request. Accommodation - June 18, 2004. After this date the block of rooms reserved for CT04 will be released to the general public, although reservations can still be made if space is available. Early booking is recommended, especially for those with accompanying persons. Extra spaces for the excursion or banquet for accompanying persons - June 30, 2004. The opening reception, excursion and banquet for delegates is included in the conference fee as well as morning and afternoon coffee breaks, lecture room rentals and other miscellaneous conference expenses. Accommodation and meals are not included in the fee. CT04 Advisory Committee: Jiri Adamek, University of Braunschweig, Germany Michael Barr, McGill University, Canada Eduardo Dubuc, University of Buenos Aires, Argentina Marco Grandis, University of Genoa, Italy George Janelidze, Capetown, South Africa Michael Johnson, Macquarie University, Australia P. T. Johnstone, Cambridge University, UK F. W. Lawvere, University at Buffalo, USA J. MacDonald, University of British Columbia, Canada S. Niefield, Union College, USA T. Porter, University of Wales, UK Jiri Rosicky, Masaryk University, Czech Republic Phil Scott, University of Ottawa, Canada Robert Seely, McGill University, Canada Art Stone, Vancouver, Canada Ross Street, Macquarie University, Australia Enrico Vitale, Louvain-la-Neuve, Belgium Walter Tholen, York University, Canada R. J. Wood, Dalhousie University, Canada This conference is being organized with help from the Pacific Institute of Mathematics(PIMS) and the UBC Conference Centre. John MacDonald, Vancouver

1 0

CFP: CMCIM 2004, WORKSHOP ON CATEGORICAL METHODS FOR CONCURRENCY, INTERACTION AND MOBILITY
by Thomas Hildebrandt 26 May '04

26 May '04

CALL FOR PAPERS AND PARTICIPATION: 3rd WORKSHOP ON: CATEGORICAL METHODS FOR CONCURRENCY, INTERACTION AND MOBILITY (CMCIM 2004), AUGUST 11, 2004 affiliated with the 10th conference in Category Theory and Computer Science (CTCS 2004) ,August 12th-14th, and Graduate Student Summer School in Category Theory and Computer Science, August 9th-11th. IT University of Copenhagen (ITU) Copenhagen, Denmark www.itu.dk/research/theory/ctcs2004/cmcim.html ------------------------------------------------------------------------ --- Important Dates: * June 21st, 2001: Submission of abstracts for CMCIM Workshop * July 1st, 2004: CTCS Registration (and special hotel rates) deadline ------------------------------------------------------------------------ ---- Just before the CTCS 2004 conference, August 11th, there will be an informal half-day workshop on Categorical Methods in Concurrency, Interaction and Mobility. The workshop has previously been held in connection with CONCUR 2002 and CONCUR 2003. We invite submissions of extended abstracts (less than 5 pages), presenting status reports, recent results, challenges or work in progress. There will be no formal proceedings of the workshop, informal proceedings will be distributed at the workshop. Thus, accepted material may be published elsewhere at a later date. Topics of interest include: • categorical algebras of processes • categorical methods in game semantics and geometry of interaction • categorical models of term/graph rewriting or rewriting logic • Chu spaces • coalgebras, bialgebras, coinduction • comparing models of concurrency • enriched categories of processes • interaction categories • bigraphs • presheaf semantics Workshop participation is free, but requires registration before 1st of July, by sending an email to hilde(a)itu.dk, containing `CMCIM2004-registration' in the subject, and your full name and affiliation in the body. Submissions should be sent before 21th of June, as PostScript files to: hilde(a)itu.dk, containing `CMCIM-submission' in the subject, and in the body the full names of the author(s), title, and a text-only abstract. CMCIM 2004 Workshop Organizers: Thomas Hildebrandt Alexander Kurz More information and registration at: http://www.itu.dk/research/theory/ctcs2004/cmcim.html --------------------------------------- SPONSORSHIP The conference and summer school are APPSEM-II events, and are as the workshop sponsored by the FIRST graduate school (www.first.dk) and the Department of Theoretical Computer Science at the IT University of Copenhagen (http://www.itu.dk/Internet/sw648.asp)

1 0

CF Participation: CTCS Conference and Summer School
by Thomas Hildebrandt 26 May '04

26 May '04

-CALL FOR PARTICIPATION-CALL FOR PARTICIPATION-CALL FOR PARTICIPATION- --- APPSEM II --- 10th CONFERENCE ON CATEGORY THEORY AND COMPUTER SCIENCE (CTCS'04) AUGUST 12-14, 2004 AND GRADUATE STUDENT SUMMER SCHOOL AUGUST 9-11, 2004 AND 3rd WORKSHOP ON CATEGORICAL METHODS FOR CONCURRENCY, INTERACTION AND MOBILITY (CMCIM 2004) AUGUST 11, 2004 IT University of Copenhagen (ITU) Copenhagen, Denmark www.itu.dk/research/theory/ctcs2004/ ------------------------------------------------------------------------ --- Important Dates: April 16th, 2004: CTCS Submission deadline (closed) June 1st, 2004: CTCS Notification of authors of accepted papers June 21st, 2001: Submission of abstracts for CMCIM Workshop July 1st, 2004: CTCS Registration (and special hotel rates) deadline ------------------------------------------------------------------------ ---- CTCS'04 is the 10th Conference on Category Theory and Computer Science, with the purpose to advance the foundations of computing using the tools of category theory. Invited Speakers for the CTCS 2004 Conference: * Francois Bergeron (Quebéc) * Martin Hyland (Cambridge) * Robin Milner (Cambridge) * Andrew Pitts (Cambridge) * Thomas Streicher (Darmstadt) Typical topics at CTCS include category-theoretic aspects of the following: coalgebras and computing concurrent and distributed systems constructive mathematics declarative programming and term rewriting domain theory and topology foundations of computer security linear logic modal and temporal logics models of computation program logics, data refinement, and specification programming language semantics type theory Previous conferences have been held in Guildford (Surrey), Edinburgh (twice), Manchester, Paris, Amsterdam, Cambridge, S. Margherita Ligure (Genova), and Ottawa. More information and registration form at: http://www.itu.dk/research/theory/ctcs2004/ ---------------------------------------------------------------------- CTCS 2004 PhD SUMMER SCHOOL The summer school is aimed at both graduate and undergraduate students, with basic knowledge of category theory. The school will offer mini-courses (5 lectures each) in: * Stone Duality, Coalgebras, and Modal Logic (Alexander Kurz) * Game Semantics (Guy McCusker) * Operational Semantics (Pawel Sobocinski) * Categorical Models for Concurrency (Thomas Hildebrandt) More information and registration at: http://www.itu.dk/research/theory/ctcs2004/summerschool.html -------------------------------------------------------------------- CMCIM 2004 WORKSHOP In between the summer school and the CTCS conference, August 11th, there will be an informal half-day workshop on Categorical Methods in Concurrency, Interaction and Mobility. The workshop has previously been held in connection with CONCUR 2002 and CONCUR 2003. We invite submissions of extended abstracts (less than 5 pages), presenting status reports, recent results, challenges or work in progress. There will be no formal proceedings of the workshop, informal proceedings will be distributed at the workshop. Thus, accepted material may be published elsewhere at a later date. Workshop participation is FREE, but requires registration before 1st of July. Submissions should be sent before 21th of June. More information and registration at: http://www.itu.dk/research/theory/ctcs2004/summerschool.html ----------------------------------------------------------------- Organisation: CTCS 2004 PROGRAMME COMMITTEE: Lars Birkedal, Chair (IT University of Copenhagen) Marcelo Fiore (University of Cambridge) Masahito Hasegawa (Kyoto University) Bart Jacobs (University of Nijmegen) Ugo Montanari (University of Pisa) Valeria de Paiva (Palo Alto Research Center) Dusko Pavlovic (Kestrel Institute) John Power (University of Edinburgh) Edmund Robinson (Queen Mary, University of London) Peter Selinger (University of Ottawa) CTCS ORGANIZING COMMITTEE E. Moggi, Chair, (Genova) S. Abramsky (Oxford) P. Dybjer (Chalmers) B. Jay (Sydney) A. Pitts (Cambridge) CTCS 2004 LOCAL ORGANIZING COMMITTEE C. Butz T. Hildebrandt A.L. Moerk CMCIM 2004 Workshop Organizers: Thomas Hildebrandt Alexander Kurz --------------------------------------- SPONSORSHIP The conference and summer school are APPSEM-II events, sponsored by the FIRST graduate school (www.first.dk) and the Department of Theoretical Computer Science at the IT University of Copenhagen (http://www.itu.dk/Internet/sw648.asp)

1 0

MPC2004: Call for participation
by Jeremy Gibbons 24 May '04

24 May '04

MPC 2004 7th International Conference on MATHEMATICS OF PROGRAM CONSTRUCTION 12--14 July, 2004, Stirling, Scotland, UK http://www.cs.cornell.edu/Projects/MPC2004 Organised in conjunction with AMAST '04 CALL FOR PARTICIPATION We are happy to announce that registration for MPC2004 is now open. Please follow the link from the conference web page (URL above). Note that the early registration deadline is Monday 14th June. After that date, we cannot guarantee that accommodation will be available. (Our apologies if you receive multiple copies of this announcement.) Jeremy Gibbons on behalf of the MPC programme committee -- Jeremy.Gibbons(a)comlab.ox.ac.uk Oxford University Computing Laboratory, TEL: +44 1865 283508 Wolfson Building, Parks Road, FAX: +44 1865 273839 Oxford OX1 3QD, UK. URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html

1 0

International Masters Program in COMPUTATIONAL LOGIC
by Int. Center for Computational Logic 24 May '04

24 May '04

International Masters Program in COMPUTATIONAL LOGIC The International Center for Computational Logic at the Technische Universitaet Dresden is offering a two-year study program, in English, leading to a master of science (M.Sc.) in computer science. This is a joint program with the Universidade Nova de Lisboa and the Technische Universitaet Wien. Courses focus on logic and constraint programming, artificial intelligence, knowledge representation and reasoning, type theory, model theory, proof theory, equational reasoning, databases, natural language processing, planning and formal methods, among others. The tuition fees are waived. At the end of the programme a research master thesis has to be prepared. Prerequisites are a good knowledge of the basics of logic, and familiarity with mathematical reasoning. Knowledge of foundations of artificial intelligence and logic programming is desirable. It is indispensable being fluent in English; German is not necessary at all, but there are facilities for studying it if desired. A bachelor in Computer Science, or equivalent degree, is required by the beginning of courses, in October 2004. Dresden, on the river Elbe, is one of the most important art cities of Germany. The economy is growing rapidly and Dresden is a top high-tech centre. AMD built the most modern chip factory in Europe, Infineon Technologies, Siemens and many other companies invest here. The possibilities of getting a job after the master are excellent. The University is very well equipped and the teachers/students ratio is close to 1. International contacts make it easy for interested students to continue pursuing a career in research. Deadline for applications is June 15, 2004, but applications are processed as they come. To apply, please send all the relevant documents by post to the address below. Further information is on the web at <http://www.cl.inf.tu-dresden.de/compulog/>. Paper information material is available on request. Please give this message broad distribution. Sylvia Epp, secretary International Center for Computational Logic Technische Universitaet Dresden, D-01062 Dresden, Germany Tel: [49] (351) 463-38341 Fax: [49] (351) 463-38342 email: cl-secretary(a)Inf.TU-Dresden.DE

1 0

existence of initial algebras
by Paul B Levy 21 May '04

21 May '04

Hi, I was teaching some students recently that there are 2 kinds of inductive definition of a set: (a) By giving an "ambient" set A, and a family of relations A^{n}-->A. This defines the least subset of A closed under all these relations, i.e. the least prefixed point of the monotone endofunction on powerset(A) mapping each subset B to the set of all elements related to B. (b) By giving a signature. This defines the initial algebra for (the endofunctor on Set determined by) the signature. I also wanted to treat the countably infinitary case, so (a) could allow relations A^{omega}-->A, and (b) could allow operations of arity omega. And I wanted to further generalize both (a) and (b) to the many-sorted setting. (Though in (a), the many-sorted situation can be reduced to the single-sorted one by taking the sum of the ambient sets.) ----------------------- I then proceeded to ask them: how do we know that (a) the least prefixed point and (b) the initial algebra exist? For (a) I gave 3 proofs: (i) take the intersection of all such subsets of A (ii) start from the empty set, and iteratively apply the monotone endofunction on the powerset of A that maps C to the set of all elements related to elements of C, taking unions at countable limit ordinals and terminating at the first uncountable limit (iii) take the set of elements of A for which there exists at least one wellfounded prooftree. For (b) I gave 2 proofs: (i) start from the empty set, and iteratively apply the signature, taking colimits at countable limit ordinals and terminating at the first uncountable limit (ii) take the set of all wellfounded operation-trees. And all these 5 proofs adapt to the coinductive setting, except that (a)(ii) and (b)(i) terminate already at omega. However, coinduction was not covered in the course. --------------------------------------- I thought that (a)(iii) and (b)(ii) were actually the most important constructions to teach the students, since they describe our basic intuition. But they require an appropriate definition of "tree". In (b)(ii), an operation-tree can be thought of a strategy for the following game: - Player picks an operation c_0 from the signature, - Opponent picks an index i_0 in the arity of c_0 - Player picks an operation c_1 from the signature etc. And, as we know, there are several equivalent ways of defining strategy. I just picked one of them: a prefix-closed set sigma of Opponent-awaiting plays c_0 i_0 c_1 i_1 ... c_n subject (in this setting) to the constraint that any Player-awaiting play c_0 i_0 c_1 i_ 1 ... c_{n-1} i_{n-1} which is consistent with sigma (i.e. every Opponent-awaiting prefix is in sigma) has a unique one-place extension in sigma. With this definition of operation-tree, it was easy to complete proof (b)(ii). And (a)(iii) is similar, except that Player moves by supplying an operation together with a tuple of A-elements. My question is: where do these tree proofs appear in the literature? Surely something so basic must appear somewhere? The best I could find, for (b), was to build a set of "terms" as a subset of an ambient set of strings (they could be strings of operations, parentheses and commas, or just strings of operations). But it is quite unnecessary to use any ambient set for (b), and, besides, that method would not work for the infinitary or coinductive cases. Paul

2 1