October 2004 - Categories - categories.org.au

Call for volunteers
by Bob Rosebrugh 01 Nov '04

01 Nov '04

Volunteers who are willing to type in TeX a part of Max Kelly's book `Basic Concepts of Enriched Category Theory' are sought. It is planned to republish the book in the TAC Reprints series. The book is about is about 250 pages, but the text is not dense on the pages. Diagrams will be handled separately, so if we had a dozen volunteers, it would probably be less than a day's work for each of them. If interested, please contact me soon. Thanks, Bob Rosebrugh

1 0

LICS 2005: Final Call for Workshop Proposals
by Alex Simpson 30 Oct '04

30 Oct '04

The deadline for LICS 2005 Workshop Proposals is November 15 --- The Twentieth IEEE Symposium on Logic In Computer Science (LICS 2005) Call for Workshop Proposals Chicago, Illinois Conference Dates: June 26-29, 2005 Workshop Dates: June 25, 2005 and June 30-July 1,2005 The Twentieth IEEE Symposium on Logic In Computer Science (LICS 2005) will be held in Chicago, Illinois, USA, June 26-29, 2005. The organizers have made arrangements for pre- and post-LICS workshops to be run in conjunction with the main conference. Possible dates are June 25 (the day before LICS) and June 30 and July 1 (the two days after LICS). Researchers and practitioners are invited to submit proposals for workshops on topics relating logic - broadly construed - to computer science or related fields. Typically, LICS workshops feature a number of invited speakers and a smaller number of contributed presentations. LICS workshops do not produce formal proceedings. However, in the past there have been special issues of journals based in part on certain LICS workshops. Proposals should include: * A short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the LICS community. * A discussion of the proposed format and agenda and the proposed duration, which may vary from half a day to two days,and preferred dates. * Procedures for selecting participants and papers. * Expected number of participants. * Potential invited speakers. * Plans for dissemination (for example, special issues of journals). * Please note that it is expected that LICS workshop organizers should be present to run their workshops. It is also assumed that normally workshop organizers (though not necessarily participants) will register for the LICS conference. Proposals are due Nov. 15, 2004 and should be submitted electronically to: Philip Scott Workshops Chair, LICS 2005 Email: phil(a)site.uottawa.ca The selections will be chosen by a committee consisting of Phokion Kolaitis (LICS General Chair), Prakash Panangaden (LICS 2005 Program Committee Chair), Phil Scott (LICS Workshop Chair) and Alan Jeffrey and Radha Jagadeesan (LICS 2005 Conference co-chairs). The results will be announced by Nov 30th, 2004. 31-Oct-2004 17:19:59 -0400,1090;000000000000-00000000

1 0

Preprint on Polarized Categories and Game Semantics
by Robert Seely 25 Oct '04

25 Oct '04

We'd like to announce the availability of the following preprint at the website <www.math.mcgill.ca/rags/> Polarized category theory, modules, and game semantics by J.R.B. Cockett and R.A.G. Seely ABSTRACT Motivated by an analysis of Abramsky-Jagadeesan games, the paper considers a categorical semantics for a polarized notion of two-player games, a semantics which has close connections with the logic of (finite cartesian) sums and products, as well as with the multiplicative structure of linear logic. In each case, the structure is polarized, in the sense that it will be modelled by two categories, one for each of two polarities, with a module structure connecting them. These are studied in considerable detail, and a comparison is made with a different notion of polarization due to Olivier Laurent: there is an adjoint connection between the two notions. ------------ We would point out (for readers interested in Type Theory) that this paper gives a variant presentation of polarized linear logic (a presentation that emphasizes slightly different aspects than Laurent's presentation, and results in a subtly different version of polarized linear logic), and provides a general semantics of that logic. The emphasis comes from the origins in Abramsky-Jagadeesan games, rather than the Hyland-Ong games that underly the intuitions in Laurent's approach. The result is a comprehensive analysis of the structure of the polarized logic, including making explicit aspects which are implicit in Laurent's approach (such as, for example, focalization). One of the novel constructions our approach permits is what we call "de-polarization": the construction of an unpolarized model from a polarized one. We also describe three families of additive connectives, which have somewhat different properties (and different polarities). -- <rags(a)math.mcgill.ca> <www.math.mcgill.ca/rags> 31-Oct-2004 17:19:59 -0400,3043;000000000000-00000000

1 0

None
by Markus Roggenbach 22 Oct '04

22 Oct '04

5 X-Accept-Language: en-us, en MIME-Version: 1.0 To: undisclosed-recipients:; Subject: categories: 2nd CFP: CALCO 2005 Content-Type: text/plain; charset=3DISO-8859-1; format=3Dflowed Content-Transfer-Encoding: 8bit X-SA-Exim-Mail-From: M.Roggenbach(a)swansea.ac.uk Sender: cat-dist(a)mta.ca Precedence: bulk We apologise if you receive multiple copies. *--------------------------------------------------------------------* * 2nd Call for Papers * * * * CALCO 2005 * * * * =091st Conference on Algebra and Coalgebra in Computer Science * * * * September 3-6, 2005, Swansea, Wales, UK * * * *--------------------------------------------------------------------* * Abstract submission : January 21, 2005 * * Technical paper submission: January 31, 2005 * * Author notification: April 11, 2005 * *--------------------------------------------------------------------* * http://www.cs.swan.ac.uk/calco/ * *--------------------------------------------------------------------* With the support of IFIP WG1.3 on Foundations of System Specification CMCS - the International Workshop on Coalgebraic Methods in Computer Science, and WADT - the Workshop on Algebraic Development Techniques, are joining their forces and reputations into a new high level bi-annual conference. Starting in 2005, CALCO will bring together researchers and practitioners to exchange new results related to foundational aspects and both traditional and emerging uses of algebras and coalgebras in computer science. CALCO 2005 will be preceded by a CALCO Young Researchers Workshop, CALCO-jnr, dedicated to presentations by PhD students and by those who completed their doctoral studies within the past few years (see www.cs.swan.ac.uk/calco-jnr/ for details). Topics of Interest ------------------ We invite submission of technical papers that report results of theoretical work on the mathematics of algebras and coalgebras, the way these results can support methods and techniques for software development, as well as experience with the transition of resulting technologies into industrial practise. We encourage submissions in topics included or related to those in the lists below. Algebras and coalgebras as mathematical objects: Automata and languages Categorical semantics Hybrid, probabilistic, and timed systems Inductive and coinductive methods Modal logics Relational systems and term rewriting Algebras and coalgebras in computer science: Abstract data types Algebraic and coalgebraic specification Calculi and models of concurrent, distributed, mobile, and context-aware computing Formal testing and quality assurance General systems theory and computational models (chemical, biological, etc) Generative programming and model-driven development Models, correctness and (re)configuration of hardware/middleware/architectures Re-engineering techniques (program transformation) Semantics of conceptual modelling methods and techniques Semantics of programming languages Validation and verification Submission Guidelines --------------------- Prospective authors are invited to submit full papers in English presenting original research. Submitted papers must be unpublished and not submitted for publication elsewhere. Experience papers are welcome, but they must clearly present general lessons learned that would be of interest and benefit to a broad audience of both researchers and practitioners. Proceedings will be published in the Springer LNCS series. Final papers will be no more than 15 pages long in the format specified by Springer. It is recommended that submissions adhere to that format and length (see at http://www.springer.de/comp/lncs/authors.html) Submissions that are clearly too long may be rejected immediately. Proofs omitted due to space limitations may be included in a clearly marked appendix. Paper submissions will be made electronically at he conference web site. Both an abstract and the full paper must be submitted by their respective submission deadlines. A special issue of Theoretical Computer Science consisting of extended versions of selected papers will be produced after the conference if there are enough good papers that can be extended and revised to the standards of this journal. Invited Speakers ---------------- The so-far confirmed invited speakers for CALCO 05 are: * Samson Abramsky, Christopher Strachey Professor of Computer Science, University of Oxford, UK. * Vladimiro Sassone, Professor of Informatics, University of Sussex, UK. Important Dates (all in 2005) ----------------------------- Jan 21 Abstract submission due Jan 31 Technical paper submissions due April 11 Author notification May 30 Camera ready due Sept 3-6 CALCO technical programme Programme Committee ------------------- Jose Fiadeiro, University of Leicester, UK (co-chair) Jan Rutten, CWI & Free University Amsterdam, NL (co-chair) Luca Aceto, Aalborg University, DK, and Reykjav=EDk University, IS Jiri Adamek, University of Braunschweig, D Christel Baier, University of Bonn, D Michel Bidoit, CNRS, Cachan, F Jules Desharnais, Laval University, CAN Marie-Claude Gaudel, LRI-CNRS, Paris, F Reiko Heckel, University of Paderborn, D H.Peter Gumm, Philipps University, Marburg, D Ugo Montanari, University of Pisa, I Larry Moss, Indiana University, Bloomington, USA Peter Mosses, BRICS and University of Aarhus, DK Fernando Orejas, Politechnical University Catalunia, Barcelona, E Francesco Parisi-Presicce, George Mason University, Fairfax, USA John Power, University of Edinburgh, UK Horst Reichel, Technical University Dresden, D Eugene Stark, Stony Brook University, New York, USA Andrzej Tarlecki, Warsaw University, PL John Tucker, University of Wales Swansea, UK Martin Wirsing, Ludwig-Maximilian University, Muenchen, D Steering Committee ------------------ Jiri Adamek, Nakagawa Ataru, Michel Bidoit, Jose Fiadeiro (co-chair), H.Peter Gumm, Bart Jacobs Hans- Jorg Kreowski, Ugo Montanari, Larry Moss, Peter Mosses, Fernando Orejas, Francesco Parisi-Presicce, John Power, Horst Reichel, Markus Roggenbach, Jan Rutten (co-chair), Andrzej Tarlecki Organising Committee -------------------- Neal Harman and Markus Roggenbach, University of Wales Swansea, UK Location and Organisation ------------------------- The City of Swansea dates from the 10th Century AD and is currently an expanding centre for high tech. industry. Swansea is located at the centre of the South Wales coastline, next to the Gower peninsula, renowned for its dramatic coastal scenery and beaches. The conference will be held on the Swansea University campus overlooking the sea. Accommodation will be available in newly built halls of residence and also in a small selection of good quality hotels. A full social programme drawing on the culture of the area will complement the scientific event. This CFP version dated: 22nd October 2004. --=20 ------------------------------------------------------------------- Markus Roggenbach Phone +44-1792-51-3578 Dept. of Computer Science Fax +44-1792-295708 University of Wales Swansea M.Roggenbach(a)Swan.ac.uk Singleton Park http://www.cs.swan.ac.uk/~csmarkus Swansea SA2 8PP, United Kingdom -------------------------------------------------------------------- 23-Oct-2004 10:16:08 -0300,1376;000000000001-00000000

1 0

Categorified Grothendieck topology
by Toby Bartels 21 Oct '04

21 Oct '04

I am familiar with the notion of Grothendieck topology on a category, and hence the concept of site as a category equipped with such. Is there an analogous concept of Grothendieck topology on a bicategory, so that a 2-site is a (weak) 2-category equipped with such? Of course, it's easy to write down a definition of SOMETHING, but it's hard to be sure that you're not missing a subtle point, at least in the weak case of a bicategory (= weak 2-category). So I'm hoping that somebody has already applied the idea, that a certain published definition is already known to be useful. A reference limited only to strict 2-categories could also be helpful. Thank you in advance for any help! -- Toby Bartels 25-Oct-2004 19:32:25 -0300,2639;000000000000-00000000

1 0

profunctors, bimodules and bipartite categories
by Claudio Hermida 19 Oct '04

19 Oct '04

There seems to be some confusion relating terminology on bimodule-equivalent structures and their actual technical definitions, so perhaps the following overview of their relationships is relevant: 1) profunctor = distributeur = bivariant functor on categories into Set, F: A^op x B -> Set 2) bimodule = two-sided discrete fibration = fibrational span <d,c>: M -> A x B (discrete fibres + cartesian liftings for d, cocartesian liftings for c + interchange) (sadly, enriched categorists, lacking generally the span notion in the V-cat setting, use (bi)modules to mean actually bivariant presheaves as in 1) 3) cospans [l,r]: A + B -> G satisfying a) l and r full and faithful b) [l,r] bijective on objects c) There are no morphisms in G from r(B) to l(A) A cospan satfisfying a-c is what might conceivably be called a `bipartite category´ (I ignore Prof. Pratt´s incarnation of this concept, but this is what it ought to be if it actually is the `same as a bimodule´). I haven´t come across this notion before, so I don´t know of any established terminology. The equivalence between 1 and 2 is a two-sided version of the Grothendieck correspondence, which as far as I know, was first made explicit in Street´s "Cosmoi of Internal Categories". The paper exhibits the passage 1 -> 2 as a weighted colimit. The converse requires, as usual, a pro-choice stance. The equivlance between 2 and 3 results from the following adjunction between Spn(A,B) and CoSpn(A,B): Ker: CoSpn(A,B) -> Spn(A,B) sends a cospan [l,r]: A + B -> G to the comma-category l/r with its two canonical projections to A and B (this is is a bimodule) Coll: Spn(A,B) -> CoSpn(A,B) sends a span <d,c>: M -> A x B to its lax colimit: it consists of functors l:A -> G and r:B -> G and a 2-cell \alpha: ld => rc, universal among such (with the evident 2-dimensional property). When <d,c> is a bimodule, G is what (I think) Bob Walters calls the collage of the bimodule. It´s rather evident how to describe G by generators and relations (as 3) above makes clear). Equally easily, Coll is left adjoint to Ker. Bimodules are recovered from their collages, M \iso l/r, and a cospan is a collage of its kernel precisely when it is a bipartite category. Incidentally, the correspondence of bimodules and bipartite categories is analogoous to the fairly useful one between bimodules bearing a monad structure and the bijective-on-object functors, obtained via the Kleisli construction on the bimodule monad (which subsumes the ordinary Kleisli construction on a monad in Cat as a special case). Claudio Hermida 19-Oct-2004 17:24:01 -0300,4986;000000000000-00000000

1 0

Complicial Sets
by Dominic Verity 19 Oct '04

19 Oct '04

Dear Colleagues, As promised many years ago, I have finally committed my proof of the "Street-Roberts" conjecture to paper. This work demonstrates that Ross Street's simplicial nerve construction provides an equivalence between the category of (strict) \omega-categories and John Roberts' category of complicial sets. A draft of this work should appear on the arXiv.org e-print sometime in the next 24 hours, but in the meantime it may be downloaded as a PDF file from http://vesuvius.ics.mq.edu.au/~domv/complicialsets.pdf Regards Dom ------------------------------------------------ A/Prof. Dominic Verity Academic Director PPDP Division of ICS Macquarie University ------------------------------------------------------------------------ ------ \\ Title: Complicial Sets Authors: Dominic Verity Comments: 129 pages Subj-class: Category Theory; Algebraic Topology MSC-class: 18D05, 55U10 (Primary) 18D15, 18D20, 18D35, 18F99, 18G30 (Secondary) \\ The primary purpose of this work is to characterise strict \omega-categories as simplicial sets with structure. We prove the Street-Roberts conjecture which states that they are exactly the ``complicial sets'' defined and named by John Roberts in his handwritten notes of that title. \\ ------------------------------------------------------------------------ ------ 19-Oct-2004 17:24:01 -0300,3590;000000000000-00000000

1 0

Abstract bimodules
by Vaughan Pratt 19 Oct '04

19 Oct '04

In my Vancouver talk at CT04 I defined a bipartite category to be a bipolar category with no morphisms from negative to positive objects. (By "bipolar" I mean having two types of objects, positive and negative, or black and white, or manic and depressive.) Robert Seely immediately remarked that this notion already had a name, namely "bimodule," which prompted me to apologize for not being familiar with that abstract usage of the notion. Since I've always associated modules (and hence bimodules) with rings (and semimodules with semirings), at the very least I'd expect this notion to be called something like "abstract bimodule" to indicate independence of any additive or even semiadditive structure. Is there an established terminology for this notion? And if not, does anyone have any strong preference between "bipartite category" and "abstract bimodule?" Note that I'll be writing initially for a CS audience, for whom bipartite graphs are a staple. Vaughan Pratt 14-Oct-2004 16:44:29 -0300,1854;000000000000-00000000

5 5

RTA'05: 3rd and last Call for Papers
by Ralf Treinen 19 Oct '04

19 Oct '04

****************************** * * * RTA'05 CALL FOR PAPERS * * * ****************************** http://www-i2.informatik.rwth-aachen.de/RTA05/ April 19--21, 2005 Nara, Japan The 16th Int. Conf. on Rewriting Techniques and Applications (RTA'05) will collocate with the 7th International Conference on Typed Lambda Calculi and Applications (TLCA'05) as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05). IMPORTANT DATES: Nov 12, 2004: Deadline for electronic submission of title and abstract Nov 19, 2004: Deadline for electronic submission of papers Jan 14, 2005: Notification of acceptance of papers Feb 4, 2005: Deadline for final versions of accepted papers Apr 19-21, 2005: Conference The deadlines are strict. RTA is the major forum for the presentation of research on all aspects of rewriting. Typical areas of interest include (but are not limited to): * APPLICATIONS: case studies; rule-based (functional and logic) programming; symbolic and algebraic computation; theorem proving; system synthesis and verification; proof checking. * FOUNDATIONS: matching and unification; narrowing; completion techniques; strategies; constraint solving; explicit substitutions; tree automata. * FRAMEWORKS: string, term, and graph rewriting; lambda-calculus and higher-order rewriting; proof nets; constrained rewriting/deduction; categorical and infinitary rewriting. * IMPLEMENTATION: compilation techniques; parallel execution; rewriting tools. * SEMANTICS: equational logic; rewriting logic. INVITED TALKS will be given at RTA'05 by: * Amy Felty (Ottawa) * Yoshihito Toyama (Sendai) * Philip Wadler (Edinburgh) BEST PAPER AWARDS AND TRAVEL GRANTS: An award of 100,000 Yen will be given to the best paper or papers as decided by the PC. A limited number of student travel grants is available. Preference will be given to students whose papers are accepted at RTA and who do not have alternative funding. Students applying for travel support should indicate this by sending an e-mail to the PC chair (giesl(a)informatik.rwth-aachen.de) together with their submission. RTA'04 PROGRAM COMMITTEE: * Franz Baader (Dresden) * Mariangiola Dezani (Torino) * Juergen Giesl (Aachen, Chair) * Bernhard Gramlich (Vienna) * Florent Jacquemard (Cachan) * Claude Kirchner (Nancy) * Pierre Lescanne (Lyon) * Aart Middeldorp (Innsbruck) * Hitoshi Ohsaki (Amagasaki) * Vincent van Oostrom (Utrecht) * Christine Paulin-Mohring (Orsay) * Frank Pfenning (Pittsburgh) * Femke van Raamsdonk (Amsterdam) * Mark-Oliver Stehr (Urbana) * Rakesh Verma (Houston) * Andrei Voronkov (Manchester) RTA'05 SUBMISSIONS: Submissions must be original and not submitted for publication elsewhere. Submission categories include regular research papers and system descriptions. Also problem sets and submissions describing interesting applications of rewriting techniques will be very welcome. The page limit is 15 pages (10 pages for system descriptions). As usual, accepted papers will appear in the Springer-Verlag Lecture Notes in Computer Science series. More information about paper submission is available at the RTA'05 web page. http://www-i2.informatik.rwth-aachen.de/RTA05/ LOCATION, TRAVEL, ACCOMMODATION, AND REGISTRATION The conference takes place in Nara park, which is one of the most important cultural sights of Japan with some of the oldest and most impressive temples and shrines. Airfares from Europe or the US to Japan are not expensive in mid-April and the conference will offer reasonably priced accommodation and low registration fees. RTA'05 PROGRAM CHAIR: Juergen Giesl LuFG Informatik II RWTH Aachen Ahornstr. 55 52074 Aachen Germany giesl(a)informatik.rwth-aachen.de RTA'05 CONFERENCE CHAIR: Hitoshi Ohsaki AIST Japan ohsaki(a)ni.aist.go.jp 19-Oct-2004 17:24:01 -0300,1462;000000000000-00000000

1 0

FMCO 2004, Formal Methods for Components and Objects: Last call for participation
by etaps02 VERIMAG 18 Oct '04

18 Oct '04

************************************************** * Third International Symposium on * * Formal Methods for Components and Objects * * (FMCO 2004) * ************************************************** DATES: 2 - 5 November 2004 PLACE: Lorentz Center, Leiden University, Leiden, The Netherlands Registration form and more information at the FMCO site http://fmco.liacs.nl/fmco04.html *** P R O G R A M *** TUESDAY 2nd, November 2004 08:45 - 09:00 Welcome 09:00 - 10:00 Keynote: Robin Milner (Cambridge University, UK) Bigraphs and their mathematics Coffee break 10:30 - 11:15 Rocco de Nicola (University of Firenze, IT) Open nets, contexts and their properties 11:15 - 12:00 Eugenio Moggi (Genova University, IT) Program generation and components Lunch break 13:30 - 14:30 Keynote: Kim Bruce (Williams College, USA) Fixing the meaning of object-oriented languages Coffee break 15:00 - 15:45 Julian Rathke (Sussex University, UK) A fully abstract trace semantics for a core Java language Coffee break 16:00 - 16:45 Martin Steffen (Kiel University, DE) Observability, classes, and object connectivity 16:45 - 17:30 Marcello Bonsangue (LIACS, NL) Roles, ports and components WEDNESDAY 3rd, November 2004 9:00 - 10:00 Keynote: Tom Henzinger (University of California, Berkeley, USA) Games with Secure Equilibria: A Theory for Component Behavior Coffee break 10:30 - 11:15 Wolfgang Weck (Software Architect, CH) Three stories from Component Hell 11:15 - 12:00 Wang Yi (Uppsala University, SE) Generation of real-time software with predictable timing behaviour Lunch break 13:15 - 14:15 Keynote: Thomas Ball (Microsoft Research at Redmond, USA) A Theory of Predicate-Complete Test Coverage and Generation Coffee break 14:30 - 15:15 Frits Vaandrager (Nijmegen University, NL) Switched Probabilistic I/O Automata 15:15 - 16:00 Susanne Graf (Verimag, FR) Specification of systems with UML and verification with Timed automata in the IF environment Social Event + Dinner THURSDAY 4th, November 2004 09:00 - 10:00 Keynote: Kim Larsen (Aalborg University, DK) t.b.a. Coffee break 10:30 - 11:15 Ed Brinksma (University of Twente, NL) Hybrid Systems and Composition: a Process Algebraic Approach 11:15 - 12:00 Andreas Podelski (Max Plank Inst. for Informatics, DE) Transition Invariants and Transition Predicate Abstraction Lunch break 13:30 - 14:30 Keynote: Chris Hankin (Imperial College, UK) Probabilistic Coordination Languages Coffee break 15:00 - 15:45 David Naumann (Stevens Institute of Technology, USA) Assertion-based encapsulation and refinement of classes 15:45 - 16:30 Tobias Nipkow (Munchen University, DE) A Machine-Checked Model for a Java-Like Language, Virtual Machine and Compiler Coffee break 16:45 - 17:30 Liu Zhiming (UNU-IIST, Macao) A Model of Refinement for Component and Object Systems FRIDAY 5th, November 2004 9:00 - 10:00 Keynote: Samson Abramsky (Oxford University, UK) Game Semantics, Open Systems and Components Coffee break 10:30 - 11:15 Luca de Alfaro (UC Santa Cruz, USA) Types for real-time components 11:15 - 12:00 Luis Barbosa (Minho University, PT) A Perspective on Component Refinement Lunch break 13:30 - 14:30 Keynote: Reinhard Wilhelm (Saarland University, DE) Timing Analysis of Hard Real-Time Systems Coffee break 15:00 - 15:45 Olaf Owe (University of Oslo, NO) CREOL: A formal language for open, distributed and object-oriented systems 15:45 - 16:30 Pierre Cointe (Ecole des Mines de Nantes, FR) From objects to aspects ORGANIZING COMMITTEE F.S. de Boer (CWI and LIACS-Leiden University) M.M. Bonsangue (LIACS-Leiden University) S. Graf (Verimag) W.P. de Roever (CAU) ----------- you received this e-mail via the address categories(a)mta.ca 19-Oct-2004 17:24:01 -0300,2156;000000000000-00000000

1 0