October 1998 - Categories - categories.org.au

Reference?
by Michael Barr 03 Nov '98

03 Nov '98

Can someone give me a reference for the fact that if the hom functor on a category factors through commutative monoids then finite products are sums and vice versa. Also conversely. Michael

4 3

Linear categories
by Michael Barr 01 Nov '98

01 Nov '98

I have checked Mac Lane's 1950 paper and I cannot find any such result. The converse, that a category in which finite sums are equivalent to products then the category takes homs in commutative monoids is sort of there, but the one I asked is not, or at least I didn't find it. However, CWM is a likely source and I will check that out. I just need some reference in any case. Michael

2 1

Unicode for math symbols (forwarded)
by Charles Wells 31 Oct '98

31 Oct '98

We have a unique chance over the next few weeks to influence various international standards bodies in presenting a complete set of mathematical and other scientific characters for inclusion in standard character sets. Much of the work for this has already been done, but there remain some problem characters on which we really need the help of the author community to describe uses and distinctions from other similar characters. Further details are available from the math society web site at: http://www.ams.org/STIX/glyphs/proposal/newsub/challenge.html The AMS has set a November 20 deadline for receipt of this information, so there is not much time to act. Thanks for your help! Arthur Smith (apsmith(a)aps.org) Research & Development, The American Physical Society (516)591-4072 Charles Wells, Department of Mathematics, Case Western Reserve University, 10900 Euclid Ave., Cleveland, OH 44106-7058, USA. EMAIL: charles(a)freude.com. OFFICE PHONE: 216 368 2893. FAX: 216 368 5163. HOME PHONE: 440 774 1926. HOME PAGE: URL http://www.cwru.edu/artsci/math/wells/home.html

1 0

Paper available
by Marta Bunge 30 Oct '98

30 Oct '98

This is to announce a new paper, by Marta Bunge and Marcelo Fiore, "Unique factorization Lifting Functors and Categories of Processes". http://www.dcs.ed.ac.uk/~mf/CONCURRENCY/ufl.dvi http://www.dcs.ed.ac.uk/~mf/CONCURRENCY/ufl.ps The paper is organised as follows. After an Introduction, Section 1 presents background material motivated from the point of view of computer science. In Section 2, the category UFL of unique factorisation lifting (ufl) functors is recalled and its basic properties are studied. Section 3 explores applications of ufl functors to concurrency. In particular we show that they may be used in the study of interleaving models like transition systems. In Section 4, we introduce triangulated categories. Our main use for them is in Section 5 where, for C a triangulated category, we exhibit the category UFL/C as a sheaf topos. These toposes may be regarded as models of linearly-controlled processes. Some concluding remarks are provided in Section 6. Professor Marta Bunge McGill University Department of Mathematics & Statistics Burnside Hall 805 Sherbrooke Street West Montreal, QC Canada H3A 2K6 Fax: (514) 933 8741 Phone: (514) 933 6191

1 0

Re: Update on FISh and shape
by Ralph Loader 29 Oct '98

29 Oct '98

> > Polymorphic quicksort in FISh is faster than in C for quicksort (see below). Some comments. You're simply not comparing like-with-like. The differences in performance that you're seeing have nothing to do with the boxing/ unboxing issues that you claim are involved. (1) Your C code compares using two floating point operations (subtraction, compare), while the fish program uses just one (no subtraction). (2) The output of the fish-to-C translation uses statically allocated memory, and won't multi-thread correctly. Sun Solaris does support multi-threading, so while your compiler uses statically allocated memory here, the Solaris C library can't. [As a matter of interest, what happens if you call your fish quicksort with a comparison function that itself calls quicksort?]. (3) The C library qsort takes a three-valued comparison function, while your fish code uses a two-valued comparison. > Shape analysis in FISh allows polymorphic functions to be specialised > to the exact shape of their arguments, so that it is never necessary > to box data structures. This can have a significant impact when the > cost of pointer-chasing is high compared to the operation being > performed. ["never"? Show me an unboxed cyclic data structure.] (4) As you note, your fish code gets optimised by specialising to the datatype and comparison function used. This is the main performance issue, and has nothing to do with boxing/unboxing issues. Note that the C library qsort is a polymorphic function, is not specialised to particular arguments, and still takes an array of unboxed elements. Specialising functions to their arguments is nothing new to FISh - some (but not all) C compilers, for instance, on inlining a function will also specialise it. The reason why the qsort function is not specialised to its arguments is because it's a precompiled library function, not because it's written in C. > The reason is that the C program achieves polymorphism by requiring > the comparison function to act on pointers, rather than values. The > actual comparison function for floats is The reality is that the machine code generated by your fish program ends up dealing with pointers also: on a typical RISC processor, to compare two doubles held in memory, you need to compute the addresses of the doubles, load them into registers and do the comparison. Passing pointers to the comparison function just means that the values are loaded into registers in the function, rather than before the function call. Whether its faster to load the values into registers before the function call or in the function will depend on things like instruction scheduling in the compiler & CPU, & register allocation in the caller & in any case the difference will be tiny. > As well as slowing down the program, these pointers are a source of It's not very often that you want to sort an array of numbers. If you want to sort some records that contain both a sort-key and some extra data, then using pointers is faster. > program clutter, potential errors, and > type violations. > > > > Ralph. (not speaking on behalf of Paradigm) Ralph Loader Paradigm Technology, Level 13, Paxus House, 79 Boulcott Steet, Wellington, New Zealand Phone: +64 4 495 1004 Fax: +64 4 499 7762

1 0

Research Positions at BRICS Research Centre and Int. PhD School
by Uffe Henrik Engberg 29 Oct '98

29 Oct '98

[Please accept our apologies if you receive this more than once] BRICS, Basic Research in Computer Science Universities of Aarhus and Aalborg Research Positions at BRICS Research Centre and International PhD School There are several research positions at BRICS starting next year, 1999. Applications are welcome by researchers in theoretical computer science and related areas, especially, but not exclusively, within the following areas: - Semantics of Computation, - Logic, - Algorithms and Data Structures, - Complexity Theory, - Data Security, - Programming Languages, - Distributed Computing, - Verification. Openings, while likely to start as postdoctoral positions, generally for 1-2 years, have the possibility of extension to longer-term positions. BRICS, Basic Research in Computer Science, is funded by the Danish National Research Foundation and consists of the BRICS Research Centre and the BRICS International PhD School. The Research Centre (Director Glynn Winskel) is a joint venture between the theoretical-computer-science groups at the universities of Aarhus and Aalborg, Denmark. The PhD School (Director Mogens Nielsen) is based in the Computer Science Department at the University of Aarhus. The BRICS Research Centre is based on a commitment to develop theoretical computer science and related mathematics, using a combination of long-term efforts and a number of short-term, intensive programmes, within carefully chosen scientific themes. The BRICS International PhD School offers a full PhD programme in computer science, including a wide range of courses, summer schools etc., and a number of PhD grants for Danish as well as foreign students. Further information on BRICS can be accessed by opening the URL: http://www.brics.dk/ The BRICS WWW entry contains information about activities, courses, PhD grants and researchers as well as access to electronic copies of information material and reports of the BRICS Series. Addresses: BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark. Telephone: +45 8942 3360 Telefax: +45 8942 3255 Internet: BRICS(a)brics.dk How to apply -------------------------------------- Applications for positions should preferably be sent by e-mail (BRICS(a)brics.dk) preferably early in January 1999, and include - curriculum vitae, and - a description of your research interests, to include, on its first page, a short say 5-10 line summary of research interests, - two or three names of referees for recommendations with the referees' + regular mail addresses and, if possible, + e-mail addresses, as well as - an URL to your WWW home directory if available. The various parts of the application (application letter, CV, etc.) can be sent by e-mail as e.g. uuencoded PDF, PostScript, clear ASCII text or if it causes trouble, just as an URL in which case we will try to load the files.

1 0

category theory and probability theory
by jean-pierre-C. 28 Oct '98

28 Oct '98

Bonjour. I am a statistician and I should be interested in a categorical framework for probability and statistical theory. Does anyone know references (books, articles, websites...) about applications of categories and functors to probability or even measure theory ? Thank you. Very truly yours, Jean-Pierre Cotton.

4 3

Please insert a d
by Dr. P.T. Johnstone 26 Oct '98

26 Oct '98

Dear All, I have been unofficially informed that "pmms", which has hitherto been an acceptable alias for "dpmms" in the domain dpmms.cam.ac.uk, is liable to stop working at some point in the near future. So, if you have my e-mail address recorded as <ptj(a)pmms.cam.ac.uk> , or anything else containing the string "@pmms", please insert a "d" in it. Peter Johnstone P.S. -- The same applies to Martin Hyland, and to anyone else you may know in this Department.

1 0

Cocompleteness of infinity categories and groupoids
by Ronnie Brown 22 Oct '98

22 Oct '98

The existence of colimits can be proved by adjoint functor type arguments: Lew Hardy and I wrote out details for the not too dissimilar situation of topological groupoids in ``Topological groupoids I: universal constructions'', {\em Math. Nachr.} 71 (1976) 273-286. Identification of vertices of a groupoid (or category) gives what Philip Higgins called a universal groupoid or category, and of course more compositions are allowed. Philip constructed this explicitly, but it also follows from the general construction. There is a mention of the cocompleteness of the multiple situation in (with P.J. HIGGINS), ``On the algebra of cubes'', {\em J. Pure Appl. Algebra} 21 (1981) 233-260. (see p. 238). Analysis and computation of colimits of various forms of multiple groupoids is necessary for applying Generalised Van Kampen Theorems - for the groupoid case this is most conveniently done in the `small' model of crossed complexes. For cat^n-groups (= n-fold categories in groups) it is probably most convenient to work in Ellis-Steiner's crossed n-cubes of groups (generalising Guin-Walery/Loday's crossed squares). Analysing pushouts of crossed squares led Loday and me to the non-abelian tensor product of groups (which act on each other). The identification of p-cells in an n-category (n>p) to give a new n-category is discussed in relation to homotopy theory in my survey ``Homotopy theory, and change of base for groupoids and multiple groupoids'', {\em Applied categorical structures}, 4 (1996) 175-193. That is, it shows how complicated and interesting are even simple cases of this general idea. We show how the n-adic Hurewicz theorem can be seen as an example of this in (with J.-L. LODAY), ``Homotopical excision, and Hurewicz theorems, for $n$-cubes of spaces'', {\em Proc. London Math. Soc.} (3) 54 (1987) 176-192. (This was the first proof of even a triadic Hurewicz theorem. The relative case goes back to early homotopy theory.) The general idea is of universally constructing an n-fold category from lower dimensional information, or lower dimensional identifications. The computational aspect (how to compute the answers) seems really interesting. One expects to be able to be more explicit in the groupoid case. On the other hand, even general double groupoids are a bit mysterious. Ronnie Brown

1 0

Re: comma?
by street＠mpce.mq.edu.au 22 Oct '98

22 Oct '98

Dear Carlos > Hi. I'm interested in following the discussion of enriched categories and >``comma objects'' on the categories list, and particularly in what you just >wrote. But...what is a ``comma category'' or more generally ``comma object''? Comma categories are explained, for example, in Mac Lane's book "Categories for the working mathematician" Grad Texts in Math #5 (Springer). In a sense they are "lax pullbacks" defined when given two functors with the same codomain. Hence, just as we can carry over the notion of pullback in Set to any category, we can carry over, by representability, the notion of comma category from Cat to any 2-category (I call them comma objects in SLNM 420). > Also, was your PhD thesis published? I used the notion of differential >graded category in a paper about vector bundles a while ago; then found out >that Kapranov et al had a few earlier papers about it, but I didn't know >that it came from even before that. Exaggerating only slightly, the whole reason enriched category theory got going in the 60s was to deal with the example of differential graded categories: these are categories enriched in chain complexes (Eilenberg-Kelly "Closed categories" LaJolla 1965). As I understand it, that example prompted Sammy and Max to their joint work: they had each used DG-categories before. My thesis [0] was not published in full. For the published papers [2], [5] on the thesis, I took out the stuff on DG-categories. However, [25] uses the DG-category approach very strongly and gives new proofs of more general results (I had some of these at the time of my thesis but hadn't included them). The papers provide universal coefficients (or homotopy classification) theorems for diagrams of chain complexes. 0. PhD Thesis: Homotopy Classification of Filtered Complexes, University of Sydney, August 1968. 2. Projective diagrams of interlocking sequences, Illinois J. Math. 15 (1971) 429-441; MR43#4881. 5. Homotopy classification of filtered complexes, J. Australian Math. Soc. 15 (1973) 298-318; MR49#5135. 25. Homotopy classification by diagrams of interlocking sequences, Math. Colloquium University of Cape Town 13 (1984) 83-120; MR86i:55025. Best regards, Ross www.mpce.mq.edu.au/~street/

1 0