January 1999 - Categories - categories.org.au

TAC 1998 contents
by TAC 16 Feb '99

16 Feb '99

[note from moderator: it is quite possible that as result of a labour dispute at Mount Allison University the categories list may be dormant for an undetermined period. I will attempt to let you know and provide alternate access to the list if this happens; thanks for your patience. regards to all, Bob] Here is the table of contents and associated information for Theory and Applications of Categories for 1998. The Editors solicit high quality contributions. THEORY AND APPLICATIONS OF CATEGORIES ISSN 1201-561X Volume 4, 1998 Pasting in multiple categories Richard Steiner 1 Protomodularity, descent and semidirect products D. Bourn and G. Janelidze 37 A theory of enriched sketches F. Borceux, C. Quinteiro and J. Rosicky 47 Simplicial and categorical diagrams, and their equivariant applications Rudolf Fritsch and Marek Golasinski 73 A 2-categorical approach to change of base and geometric morphisms II A.Carboni, G.M.Kelly, D.Verity and R.J.Wood 82 The separated extensional Chu category Michael Barr 137 Applications of Peiffer pairings in the Moore complex of a simplicial group A. Mutlu and T. Porter 148 Freeness Conditions for 2-Crossed Modules and Complexes A. Mutlu and T. Porter 174 Geometric Construction of the Levi-Civita Parallelism Anders Kock 195 On Generic Separable Objects Robbie Gates 174 Copyright 1998 The Editors of Theory and Applications of Categories THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format. Subscription information: Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be e-mailed to new subscribers and are available by tt WWW/ftp. To subscribe, send e-mail to tac(a)mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh(a)mta.ca. Information for authors: The typesetting language of the journal is TeX, and LaTeX is the preferred flavour. TeX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal's WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac(a)mta.ca to receive details by e-mail. Editorial board: John Baez, University of California, Riverside: baez(a)math.ucr.edu Michael Barr, McGill University: barr(a)triples.math.mcgill.ca Lawrence Breen, Universite de Paris 13: breen(a)math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown(a)bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb(a)math.psu.edu Aurelio Carboni, Universita dell Insubria: carboni(a)fis.unico.it P. T. Johnstone, University of Cambridge: ptj(a)pmms.cam.ac.uk G. Max Kelly, University of Sydney: kelly_m(a)maths.usyd.edu.au Anders Kock, University of Aarhus: kock(a)imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere(a)acsu.buffalo.edu Jean-Louis Loday, Universit e de Strasbourg: loday(a)math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk(a)math.ruu.nl Susan Niefield, Union College: niefiels(a)union.edu Robert Pare, Dalhousie University: pare(a)mscs.dal.ca Andrew Pitts, University of Cambridge: ap(a)cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh(a)mta.ca Jiri Rosicky, Masaryk University: rosicky(a)math.muni.cz James Stasheff, University of North Carolina: jds(a)charlie.math.unc.edu Ross Street, Macquarie University: street(a)macadam.mpce.mq.edu.au Walter Tholen, York University: tholen(a)mathstat.yorku.ca Myles Tierney, Rutgers University: tierney(a)math.rutgers.edu Robert F. C. Walters, University of Sydney: walters_b(a)maths.usyd.edu.au R. J. Wood, Dalhousie University: rjwood(a)mscs.dal.ca

2 1

CFP: PDPTA-99 Codesign Session
by eric＠iis.sinica.edu.tw 01 Feb '99

01 Feb '99

=========================================== S E C O N D C A L L F O R P A P E R S =========================================== SPECIAL SESSION ________________________________________________________________ "HARDWARE-SOFTWARE CODESIGN OF PARALLEL AND DISTRIBUTED SYSTEMS" ________________________________________________________________ "http://www.iis.sinica.edu.tw/~eric/pdpta99-codesign/" The 1999 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'99) June 28 - July 1, 1999 Monte Carlo Resort, Las Vegas, Nevada, USA A special session on the HARDWARE-SOFTWARE CODESIGN of parallel and distributed systems is being organized at PDPTA'99, which will be held in Las Vegas, Nevada, U.S.A., June 28 - July 1, 1999. Architectures supporting parallel and distributed computing include both hardware and software. The success of such architectures depends significantly on how the hardware and software interact. This in turn requires careful codesign approaches which include co-partitioning, scheduling, co-synthesis, co-simulation, and co-verification. Due to their complex behavior and structural restrictions, parallel and distributed systems present a greater challenge to codesign methodologies than conventional systems. Object-oriented modeling/design, formal specification/verification methods, graph-theoretic analysis, virtual prototyping, functional/structural partitioning are some promising techniques which can be employed for hardware-software codesign. Parallel and distributed processing is the computing trend and hardware-software codesign is the technique for supporting this trend. SESSION SCOPE: All hardware-software codesign related topics that deal with parallel and distributed systems are invited. Topics of interest include, but are not limited to, the following: * Specification/Modeling * Object-Oriented Technology * Co-design Methodologies/Tools * Parallel/Distributed Techniques * Co-partitioning * Virtual Prototyping * Related Software Synthesis * Rapid Prototyping * Related Hardware Synthesis * High-Assurance Systems * Co-simulation and Validation * IP / Virtual Components * Co-verification and Testing * Embedded/Real-Time Systems SUBMISSION OF PAPERS: To submit a paper to the special session, please do the following: (1) Prepare a manuscript in PDF/PostScript/Microsoft Word-7.0 format of maximum 7 pages: single-spaced, single-column, US-Letter/A4 size, with title, authors, affiliations, e-mail addresses, and a 100-word abstract on the first page. (2) Send an ascii-text e-mail with the paper title and the corresponding author's name, mailing address, e-mail address, and telephone/fax numbers. (3) E-mail the above two to: "eric(a)iis.sinica.edu.tw". If electronic submission is not possible, please mail the above to the following address: Dr. Hsiung, Pao-Ann (Mailbox A-38) Institute of Information Science Academia Sinica No. 128, Sec. 2, Academic Road Nankang, Taipei 115, TAIWAN, R.O.C. (4) Important Dates: Submission Deadline: March 1, 1999 Paper Notification: April 1, 1999 Camera-Ready papers: May 1, 1999 Pre-Registration: May 1, 1999 PDPTA'99 Conference: June 28-July 1, 1999 (5) A minimum of 6 and a maximum of 24 papers will be accepted for the special session. All submissions will be reviewed by at least 2 referees. Papers must not have been previously published or currently submitted for publication elsewhere. Pre-registration at the conference is a must for all accepted papers to be published in the proceedings. All accepted papers must be presented at PDPTA'99, Las Vegas, Nevada, U.S.A. PUBLICATION: The conference proceedings will be published by CSREA Press (ISBN). It will be a multivolume set. The proceedings will be available at the conference. All accepted papers will also be considered for journal publication (soon after the conference). ORGANIZERS/SPONSORS: A number of university faculty members and their staff in cooperation with the Monte Carlo Resort (Conference Division, Las Vegas ), will be organizing the conference. The conference is sponsored by the Computer Science Research, Education, and Applications Press (CSREA: USA Federal EIN # 58-2171953) in cooperation with the National Supercomputing Center for Energy and the Environment (Department of Energy, USA), The International Association for Mathematics and Computers in Simulation (IMACS), The International Technology Institute (ITI), The Java High Performance Computing research group (JHPC; www.jhpc.org) the Computer Vision Research and Applications Tech. (CVRA), developers of high-performance machines and systems (pending) and other related computer associations (pending.) LOCATION OF CONFERENCE: The conference will be held in the Monte Carlo Resort hotel, Las Vegas, Nevada, USA. This is a mega hotel with excellent conference facilities and over 3000 rooms. The hotel is minutes from the Las Vegas airport with free shuttles to and from the airport. This hotel has many vacation and recreational attractions, including: waterfalls, casino, spa, pools & kiddie pools, sunning decks, Easy River water ride, wave pool with cascades, lighted tennis courts, health spa (with workout equipment, whirlpool, sauna, ...), arcade virtual reality game rooms, nightly shows, snack bars, a number of restaurants, shopping area, bars, ... Many of these attractions are open 24 hours a day and most are suitable for families and children. The negotiated hotel's room rate for conference attendees is very reasonable ($79 + tax) per night (no extra charge for double occupancy) for the duration of the conference. The hotel is within walking distance from most other Las Vegas attractions (major shopping areas, recreational destinations, fine dining and night clubs, free street shows, ...). For the benefit of our international colleagues: the state of Nevada neighbors with the states of California, Oregon, Idaho, Utah, and Arizona. Las Vegas is only a few driving hours away from other major cities, including: Los Angeles, San Diego, Phoenix, Grand Canyon, ... EXHIBITION: An exhibition is planned for the duration of the conference. We have reserved 20+ exhibit spaces. Interested parties should contact H. R. Arabnia (address is given below). All exhibitors will be considered to be the co-sponsors of the conference. Each exhibitor will have the opportunity to include a two-page description of their latest products in the conference proceedings (if submitted by May 1, 1999). MEMBERS OF PROGRAM & ORGANIZING COMMITTEES: The Program Committee is currently being formed. Those interested in joining the Program Committee should email H. R. Arabnia (hra(a)cs.uga.edu) the following information: Name, affiliation and position, complete mailing address, email address, tel/fax numbers, a short biography together with research interests. SESSION CHAIR/ORGANIZER: Address: Dr. Pao-Ann Hsiung Institute of Information Science Academia Sinica No. 128, Sec. 2, Academic Road Nankang, Taipei 115, TAIWAN, R.O.C. E-mail: eric(a)iis.sinica.edu.tw Tel. : +886-2-27883799 Fax : +886-2-27824814 URL : http://www.iis.sinica.edu.tw/~eric/pdpta99-codesign/ CONFERENCE CONTACT: Hamid R. Arabnia The University of Georgia Department of Computer Science 415 Graduate Studies Research Center Athens, Georgia 30602-7404, U.S.A. Tel: (706) 542-3480 Fax: (706) 542-2966 E-mail: hra(a)cs.uga.edu URL: http://www.jhpc.org/pdpta/

2 1

Reading advise on bicategory theory
by Lars Lindqvist 01 Feb '99

01 Feb '99

Hi, I am looking for advise on suitable litterature for a beginner in bicategory-theory. The litterature I have found so far is: Kelly, Street Review of the elements of 2-categories Borceux Handbook of categorical algebra 1 I have also ordered the following article: Benabou Introduction to bicategories So far I have only read Borceux's book but it contains mainly definitions. In particular I have difficulties understanding the need for (and consequences of) the coherence axioms associated with the natural isomorphisms expressing the associativity and identity 'axioms'. /Lars Lindqvist

3 2

Paper Announcement
by Alex Simpson 01 Feb '99

01 Feb '99

The following paper is available by anonymous FTP or over the Web Lambda Definability with Sums via Grothendieck Logical Relations by Marcelo Fiore and Alex Simpson We introduce a notion of *Grothendieck logical relation* and use it to characterise the definability of morphisms in *stable* bicartesian closed categories by terms of the simply-typed lambda calculus with finite products and finite sums. Our techniques are based on concepts from topos theory, however our exposition is elementary. The paper is written in a style appropriate for the conference Typed Lambda-Calculi and Applications where it is to be presented in April. However, we briefly discuss the true categorical content of the paper, which will be further expanded upon in a full version of the paper (forthcoming). The paper is available over the Web: http://www.dcs.ed.ac.uk/~mf/TYPES/glr.{dvi,ps} http://www.dcs.ed.ac.uk/~als/Research/glr.ps.gz or by anonymous FTP: ftp://ftp.dcs.ed.ac.uk/pub/mf/TYPES/glr.{dvi,ps} ftp://ftp.dcs.ed.ac.uk/pub/als/Research/glr.ps.gz Best wishes for a happy New Year, Alex Simpson -- Alex Simpson, LFCS, Division of Informatics, University of Edinburgh Email: Alex.Simpson(a)dcs.ed.ac.uk Tel: +44 (0)131 650 5113 FTP: ftp.dcs.ed.ac.uk/pub/als Fax: +44 (0)131 667 7209 URL: http://www.dcs.ed.ac.uk/home/als

2 2

Pullback perserving functor
by Hongseok Yang 30 Jan '99

30 Jan '99

Would someone let me know the answer and the proof or counter example of the following question? Suppose the category C has a pullback for every pair of morphism (f : X -> Y, g : W -> Y). Let K be the full subcategory of the functor category Func(C,Set) whose objects are pullback perserving functors. Is K ccc? (If so, how I can show this?) Thanks, Hongseok

3 2

Barry Jay's question
by Michael Barr 29 Jan '99

29 Jan '99

Unless I am missing something, it seems to me that for any CCC C with finite limits and any finite category I, the functor category C^I is a CCC. You can also replace finite by any cardinal if you do it in both places. The argument is roughly this. Let |I| denote the discrete category with the objects of I. The inclusion |I| --> I induces U: C^I --> C^{|I|} and the limits imply the existence of a right adjoint R of U. Since U also preserves limits, the cotriple (UR,e,d) preserves finite limits. It is easy to see that U is cotripleable and that C^{|I|} is a CCC and, hence, so is C^I. For define A -o RC = R(UA -o C). For a general object B, the line B --> URB ==> URURB is an equalizer and you can define A -o B as the equalizer of A -o URB ==> A -o URURB. Michael ------------------------------------------------------------------- History shows that the human mind, fed by constant accessions of knowledge, periodically grows too large for its theoretical coverings, and bursts them asunder to appear in new habiliments, as the feeding and growing grub, at intervals, casts its too narrow skin and assumes another... Truly the imago state of Man seems to be terribly distant, but every moult is a step gained. - Charles Darwin, from "The Origin of Species"

1 0

Generalized Enrichment
by Tom Leinster 29 Jan '99

29 Jan '99

The following is now available, at http://www.dpmms.cam.ac.uk/~leinster/ Generalized Enrichment for Categories and Multicategories In this paper we answer the question: `what kind of a structure can a general multicategory be enriched in?' (Here `general multicategory' is used in the sense of the author, Burroni or Hermida.) The answer is, in a sense to be made precise, that a multicategory of one type can be enriched in a multicategory of the type one level up. In particular, we will be able to speak of a T_n-multicategory enriched in a T_{n+1}-multicategory, where T_n is the monad expressing the pasting-together of n-opetopes. The answer for general multicategories reduces to something surprising in the case of ordinary categories: a category may be enriched in an `fc-multicategory', a very general kind of 2-dimensional structure encompassing monoidal categories, plain multicategories, bicategories and double categories. It turns out that fc-multicategories also provide a natural setting for the bimodules construction. We also explore enrichment for some multicategories other than just categories. An extended application is given: the relaxed multicategories of Borcherds and Soibelman are explained in terms of enrichment. Tom Leinster PS - There's been the odd problem in the past with the web address; if it doesn't work, try substituting "can" for "www", or send me an email.

1 0

Conference Announcement BCTCS 15
by John G. Stell 29 Jan '99

29 Jan '99

___________________________________________________________________________ CALL FOR CONTRIBUTIONS AND PARTICIPATION 15th British Colloquium for Theoretical Computer Science (BCTCS 15) 14th - 16th April 1999 at Keele University Supported by EPSRC and the London Mathematical Society ___________________________________________________________________________ INVITED SPEAKERS: Wan Fokkink (Swansea) Martin Hofmann (Edinburgh) Bill McColl (Oxford) Ian Pratt (Manchester) David Pym (QMW, London) Glynn Winskel (Aarhus) Mike Worboys (Keele) ___________________________________________________________________________ CONTRIBUTED TALKS Contributions are sought on any aspect of theoretical computer science. Research areas within the scope of BCTCS include, but are not limited to, the following list: Concurrency, types, semantics, formal methods, computational complexity, algorithms, discrete mathematics, proof theory and logic, artificial intelligence, database theory, theorem proving, symbolic computation and experimental work. This year for the first time, authors will have the option to submit papers based on their talks to a special issue of the Journal of Universal Computer Science. However, the meeting will retain its informal character, and it will still be possible for researchers to give a presentation at the meeting but not have their paper considered for publication. Submission of papers for publication will take place at some stage after the meeting. Besides talks from established researchers, BCTCS meetings provide a forum for young researchers who may wish to give a presentation but who may feel that the body of their work is not yet substantial enough for publication. ___________________________________________________________________________ SUPPORT FOR POSTGRADUATE STUDENTS A limited number of fully funded places are available to postgraduate students who are supported by EPSRC. For other students there is a SPECIAL REDUCED RATE for the meeting, and some additional financial support may be available in special cases. ___________________________________________________________________________ FURTHER DETAILS Further details, including registration forms, prices, and forms for submission of contributed talks, are available from the BCTCS15 web page: http://www.keele.ac.uk/depts/cs/Announcements/bctcs/ The web page also has links to previous BCTCS meetings, which provide a useful guide to the wide range of topics which have been covered by past contributions. BCTCS15 is organized by John Stell, who can be contacted by email: john(a)cs.keele.ac.uk or at: Department of Computer Science, Keele University, Keele, Staffs, U. K., ST5 5BG. ___________________________________________________________________________

1 0

Maude 1.00 Release
by Jose Meseguer 29 Jan '99

29 Jan '99

The Maude system, its documentation, a collection of examples, and a list of related papers are available (free of charge) on the web at http://maude.csl.sri.com Maude is a high-performance reflective language and system supporting both equational and rewriting logic specification and programming for a wide range of applications. Maude has been influenced in important ways by the OBJ3 language, which can be regarded as an equational logic sublanguage. Besides supporting equational specification and programming, Maude also supports rewriting logic computation. Rewriting logic is a logic of concurrent change that can naturally deal with state and with concurrent computations. It has good properties as a general semantic framework for giving executable semantics to a wide range of languages and models of concurrency. In particular, it supports very well concurrent object-oriented computation. The same reasons making rewriting logic a good semantic framework make it also a good logical framework, that is, a metalogic in which many other logics can be naturally represented and executed. Maude supports in a systematic and efficient way logical reflection. This makes Maude remarkably extensible and powerful, supports an extensible algebra of module composition operations, and allows many advanced metaprogramming and metalanguage applications. Indeed, some of the most interesting applications of Maude are metalanguage applications, in which Maude is used to create executable environments for different logics, theorem provers, languages, and models of computation. %%% Please, excuse the inconvenience if you received multiple copies.

1 0

two questions about universal quantification
by Barry Jay 28 Jan '99

28 Jan '99

Can anyone help with the following two questions? Barry Jay Question 1 ~~~~~~~~~~ Has the following lemma been seen before? Lemma: If D is a cartesian closed category having all finite limits then so is its arrow category. Proof Finite limits in the arrow category are constructed pointwise. Arrows from a: A -> I to b: B-> J In the arrow category are given by commuting squares (all vertical lines are arrows pointing down) f A -----> B | | a| |b | | I -----> J u The object of such appropriate pairs (f,u) is given by the pullback E -----> A->B | | | | A->b | | I->J ---> A->J a->J The universal property follows directly. QED The proof uses a form of universal quantification over A. Similar constructions arise with the use of ends and dinatural transformations. I also used them aggresively in my paper on data categories (http://linus/~cbj/Publications/data_categories.ps.gz) to quantify over all paths through a tree. The lemma generalises to other functor categories over D provided there are sufficient limits in D to express all of the constraints. Question 2 ~~~~~~~~~~ The proof above shows how pullbacks and cartesian closure interact to provide a form of universal quantification. Call this new construction quantification by exponentiation. What is its expressive power? Discussion ~~~~~~~~~~ Universal quantification wrt an arrow f : X -> Y is usually given as a right adjoint to the functor D/Y --> D/X which pulls back along f. Call this quantification by adjunction. When it is specialised to a projection XxY ---> X then it can be thought of as quantification over the object Y. Quantification by exponentiation can be seen as supplying some of the ingredients necessary for this special case. For example, consider the equaliser E of two functions into an exponential: f,g : X --> (A->B) If the quantifier by adjunction exists for the projection XxA ---> X then E is given by applying it to the equaliser of the uncurried forms of f and g from XxA to B. Motivation ~~~~~~~~~~ One the one hand, this structure is weaker than that normally assumed, which may sometimes be a good thing. On the other hand, the power resulting from this combination of features may still be more than desired. Many models of computation assume both cartesian closure and and all finite limits but this is already more than we need to model the types of most languages, i.e. a type corresponding to one of the objects produced by quantification by exponentiation would have undecidable membership, so that values would need to come equipped with a proof of their membership. So (assuming that cartesian closure is a given) the question becomes whether there is a smaller class of limits which are good enough to model programming languages. One candidate is to work in an extensive category, in which only pullbacks along coproduct inclusions are presumed. A short argument shows that if Z has decidable equality then any cospan over it has a pullback. Actually, there is a rich, but under-explored class of pullbacks implied by this innocuous assumption. For example, the list functor preserves such pullbacks (this is not quite trivial). There may well be other, better candidates. I would be glad to hear of them. ************************************************************************* | Associate Professor C.Barry Jay, | | Reader in Computing Sciences Phone: (61 2) 9514 1814 | | Head, Algorithms and Languages Group, Fax: (61 2) 9514 1807 | | University of Technology, Sydney, e-mail: cbj(a)socs.uts.edu.au | | P.O. Box 123 Broadway, 2007, http://www-staff.socs.uts.edu.au/~cbj | | Australia. FISh homepage ... ~cbj/FISh | *************************************************************************

3 2