May 1998 - Categories - categories.org.au

Informal seminar: Trieste
by Pedicchio M. Cristina 19 May '98

19 May '98

Bill Lawvere will be in Italy in July 98, so I am planning to organize an informal Seminar on the 10-11 of July in Trieste. A few European colleagues have already announced their participation; I welcome all interested people to participate. Please contact me by e-mail at the address pedicchi(a)univ.trieste.it M.Cristina Pedicchio"

1 0

fibrational theory of geometric morphisms
by Thomas Streicher 13 May '98

13 May '98

A(n attempt of a) systematic exposition of the basics of a Fibrational Theory of Geometric Morphisms based essentially on the work of B'enabou, Moens et. al. can be found in the diploma thesis of my student Peter Lietz under the www-address http://www.mathematik.tu-darmstadt.de/ags/ag14/mitglieder/lietz-de.html A new aspect seems to be that Moens' characterisation of geometricity of a fibration is essentially extensivity of the fibred category albeit w.r.t. internal sums. Thomas Streicher

1 0

Re: Multicategories
by Michael MAKKAI 13 May '98

13 May '98

On Sat, 9 May 1998, Apostolos Syropoulos wrote: > Dear Category Theorists, > > I am currently studying a paper on logic and the author employs > category theory in his work. However, he is using > "multicategories" which is something I hear for the first time. > Unfortunately my knowledge of CT isn't that deep and so > if someone could suggest me papers/books that provide > a definition of this term, I would be really grateful to him/her! > > Yours Sincerely, > > A. S. > > -- > **************************************************************** > *Apostolos Syropoulos * > *snail mail: 366, 28th October Str., GR-671 00 Xanthi, HELLAS * > *email : apostolo(a)obelix.ee.duth.gr * > *phone num.: +-30-(0)541-28704 * > *home page : http://obelix.ee.duth.gr/+AH4-apostolo * > **************************************************************** > > > Here are two references to multicategories, both by Joachim Lambek: "Deductive systems and categories II", Springer Lecture Notes in Mathematics. no.86, pp. 76-122 (1969) "Multicategories revisited", In: Categories in Computer Science and Logic, Proceedings, Boulder 1987; Contemporary Math 92, AMS; pp. 217-240 (1989). Michael Makkai

1 0

None
by esik＠inf.u-szeged.hu 13 May '98

13 May '98

>>From esik Tue May 12 16:09:55 +0200 1998 remote from inf.u-szeged.hu To: rrosebrugh(a)mta.ca cc: esik Subject: FICS 2nd announcement Date: Tue, 12 May 1998 16:09:55 +0200 From: Esik Zoltan <esik(a)inf.u-szeged.hu> Received: from inf.u-szeged.hu by inf.u-szeged.hu; Tue, 12 May 1998 16:09 MET Content-Type: text Content-Length: 4630 Dear Professor Rosebrugh, Would you please forward the attached 2nd announcement of the FICS workshop to the subsribers of categories. Thank you in advance. Yours sincerely, Zoltan Esik ******************************************************************************* ******************************************************************************* ** ** ** F I C S ' 9 8 ** ** ** ** Fixed Points in Computer Science ** ** ** ** A Satellite Workshop to MFCS'98 ** ** ** ** August 27-28, 1998, Brno, Czech Republic ** ** ** ** Second Announcement ** ** ** ******************************************************************************* ******************************************************************************* Aim: Fixed points play a fundamental role in several areas of computer science, and the construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop is to provide a forum for researchers to present their results to those members of the computer science community who study or apply the fixed point operation in the different fields and formalisms. Topics: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, fixed points in process algebras and process calculi, regular algebra of finitary and infinitary languages, formal power series, tree automata and tree languages, infinite trees, the mu-calculus and other programming logics, fixed points in relation to dataflow and circuits, fixed points and the lambda calculus. Invited lectures: A. Arnold (Bordeaux): Boolean mu-calculus and its relations with model-checking and games J. W. de Bakker (Amsterdam): Fixed points in metric semantics Y. N. Moschovakis (Los Angeles/Athens): Fair, non-deterministic recursion in higher types (tentative) Program Committee: R. Backhouse (Eindhoven) S. L. Bloom (Hoboken) C. Boehm (Rome) R. De Nicola (Florence) Z. Esik (Szeged, chairman) P. Freyd (Philadelphia) I. Guessarian (Paris) D. Kozen (Cornell) W. Kuich (Vienna) M. Mislove (Tulane) R. F. C. Walters (Sydney) Contact person: Zoltan Esik Dept. of Computer Science Jozsef Attila University P.O.B. 652 6701 Szeged, Hungary e-mail: fics(a)inf.u-szeged.hu phone: ++36-62-454-289 fax: ++36-62-312-292 Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to the PC chair. Electronic submissions in the form of uuencoded postscript file are encouraged and can be sent to fics(a)inf.u-szeged.hu. Submissions are to be received before May 25, 1998. Authors will be notified of acceptance by June 25, 1998. Proceedings: Preliminary proceedings containing the abstracts of the talks will be available at the meeting. Publication of final proceedings as a special issue of Theoretical Informatics and Applications depends on the number and quality of the papers. The workshop will be organised at the same place as the federated MFCS'98/CSL'98 conference and care will be taken that participants of the workshop can attend invited talks of the MFCS and CSL conferences. No special registration fee is required for participants who also register for MFCS'98 or CSL'98 and have a presentation at the workshop. Other workshop participants registered for MFCS'98 or CSL'98 will be requested to pay a small fee for the preliminary proceedings. Registration only for the workshop is also possible--expenses for fee, accommodation, and basic meals are very modest. Registration information can be found on the MFCS web page at http://www.fi.muni.cz/mfcs98. Organising Committee: L. Bernatsky (Szeged) A. Kucera (Brno) T. Szeles (Szeged) More information is available at the following web sites: http://www.inf.u-szeged.hu/fics/ http://www.cs.stevens-tech.edu/CFP/FICS/

1 0

PSSL 68
by Jiri Rosicky 12 May '98

12 May '98

********* First Announcement ********* The 68th Peripatetic Seminar on Sheaves and Logic August 29-30, 1998 Brno, Czech Republic The 68th meeting of the PSSL will be held at the Masaryk University, Brno, Czech Republic over the weekend of 29-30 August 1998. It is organized in connection with the federated conferences MFCS (Mathematical Foundations of Computer Science) and CSL (Computer Science Logic) which are taking place in Brno during August 23-28, 1998. There are other workshops related to MFCS\CSL and participants interested to stay in Brno the whole week may contact Jan Staudek. As usual, the 68th meeting of the PSSL will be informal in nature and it will be focused on category theory, logic and theoretical computer science. We have arranged an accommodation in a student dormitory (single rooms, for 2 nights since Friday to Sunday) together with breakfasts and lunches in a university restaurant. The cost is 80$ for those who will register till June 25th and 120$ for others. Participants wishing to stay in hotels should contact Jan Staudek. Brno is located about 200 km south-east of Prague and 130 km north of Vienna and it can be reached from the both airports by trains and buses. More details will be available in the second announcement. We will maintain a www-page containing all informations. The registrations for PSSL 68 are handled electronically via web, on http://www.fi.muni.cz/usr/staudek/mfcs/, or via e-mail. To use the web, all you have to do is to carefully fill out the form located there using Netscape 2.0 / Explorer 3.0 or later (with Java Script enabled). To register via e-mail, please fill out the form below and return it (preferably by e-mail) to Jan Staudek (staudek(a)fi.muni.cz) We would be pleased if you could register till June 25th. Looking forward to meeting you in Brno. Jiri Rosicky and Jan Paseka Postal address: Jan Paseka Department of Mathematics Masaryk University Janackovo nam. 2a 66295 Brno Czech Republic email: paseka(a)math.muni.cz www: http://www.math.muni.cz/ftp/ftp/pub/math/people/Paseka/pssl68/pssl68.html (the both addresses can be used for everything concerning PSSL, except the registration) _________________________________________________________________ 68th PSSL/MFCS Registration Form (e-mail) ----------------------------------------- I want to attend the 68th PSSL in Brno Name: Address: email: I wish to give a talk entitled: I wish to have the PSSL accommodation and meals: Special dietary requirements: __________________ Method of payment (all payment in US dollars): ---------------------------------------------- [] VISA [] MASTERCARD [] EUROCARD Please note that the amount your card will be charged depends on the actual change rate. Please make signed this Registration Form and send it to Faculty of Informatics MU MFCS, Jan Staudek Botanicka 68a 602 00 Brno, Czech Republic Amount to be payed: ________________ Cardholder's name: ---------------- Card no.: _________________ Exp: __/__/__ Sign:_____________________ [] Bank Checque / Eurochecque Please make check payable in US dollars to "Faculty of Informatics, Masaryk University" enclosed to signed this Registration Form and send all to Faculty of Informatics MU MFCS, Jan Staudek Botanicka 68a 602 00 Brno, Czech Republic Sign:_____________________ [] Bank transfer to Komercni banka, a.s. pobocka Brno-mesto nam. Svobody 21 631 31 Brno, Czech Republic SWIFT Code: KOMBCZPP Account Number: 85636621/0100 Account Number: 1234567890-1234567890 Details of Payment (Mandatory): 3375000498, < name > Be sure to clearly state 3375000498 and your name in Details of Payment. Amount of Payment : $ __________ Amount of Payment : __________ Kc For Czech participants (in accordance with current currency rate) Expected Date of Payment : ------------ _______________________________________________________________ ----- End of forwarded message from Jan Paseka -----

1 0

Re: the FISh language
by Frode Odegard 12 May '98

12 May '98

The right URL appears to be: http://www-staff.socs.uts.EDU.AU:8080/~cbj/FISh/Announcement/ Best regards, Frode Odegard -- .......................................................... Frode Odegard - frode(a)odegard.com - http://www.odegard.com

1 0

the FISh language
by Barry Jay 11 May '98

11 May '98

[apologies for multiple announcements] *********************************** * Functional = Imperative + Shape * *********************************** FISh is a new array programming language that combines (and extends) the EXPRESSIVE POWER of functional programming with the EFFICIENT EXECUTION of imperative, or procedural, programming by performing STATIC SHAPE ANALYSIS on all programs. This shape computation reduces higher-order functional programs to simple imperative forms, i.e. F - Sh = I. Conversely, FISh works best when functions are constructed from imperative procedures and shape functions, as recommended by the slogan that gives the language its name. F = I + Sh FISh execution speeds on typical array problems are SEVERAL TIMES FASTER than other higher-order, polymorphic languages. This announcement, research papers, reference material and the implementation are all available from http://linus.socs.uts.edu.au/~cbj/FISh/announcement.html The main themes are introduced in the paragraphs below. Barry Jay http://linus.socs.uts.edu.au/~cbj *********************************** Expressive Power ~~~~~~~~~~~~~~~~ FISh supports - the usual functional features such as strong typing, higher-order functions and parametric polymorphism. It also supports - simple imperative features such as assignment, for- and while-loops, and local variables, using a type of commands. Procedures are represented as functions into commands, as in Algol-like languages. Unlike existing Algol-like languages, it also supports data types of arrays, so that array programs may be polymorphic in the size of the array. Now this has been extended to support - poly-dimensional array programming. If a is any array type then [a] is the type of all arrays with entries in a that are - finite dimensional, and - regular, such as vectors, matrices, three-dimensional arrays, etc. Thus, poly-dimensional array programs can be written that act on a vector, matrix, or higher-dimensional array. For example, the standard prelude supports a polymorphic constant map : (a -> b) -> [a] -> [b] which will map a function over a vector, matrix, or higher-dimensional array. Note that a matrix of integers, or type [int] has a different type from a vector of vectors of type [[int]]. Thus, given sum_int : [int] -> int which adds up an array of integers, we have map sum_int : [[int]] -> [int] which will sum each entry of the outer array. This is useful when - representing complex numbers as arrays of length 2, or - each entry in an array has an associated array of data, e.g. - each entry is given an array of nearest neighbours, or - decomposing an array into an array of blocks, e.g. - a matrix into a matrix of matrices. Efficiency ~~~~~~~~~~ ------------------------------------------------------------- | |Map Reduce Q'sort FFT MM-loops MM-ip | |_______________|____________________________________________| |---------------|--------------------------------------------| |FISh |1.04 0.37 1.93 3.57 4.36 7.05 | |---------------|--------------------------------------------| |Ocaml(in-lined)|4.00 2.66 3.53 | |---------------|--------------------------------------------| |Ocaml |5.99 4.59 15.47 8.16 7.71 60.61 | |---------------|--------------------------------------------| |speedup |5.8 12.4 8.0 2.3 1.8 8.6 | -------------------------------------------------------------- Benchmark user times See http://linus.socs.uts.edu.au/~cbj/FISh/Benchmarks for more details. Static Shape Analysis ~~~~~~~~~~~~~~~~~~~~~ Shape analysis is used to determine the number of dimensions, and the size in each dimension, of every array appearing in a program. (A program is a closed term of array or command type.) In particular, it checks that every array is regular, i.e. is a hyper-cube whose entries all have the same shape. The latter requirement is necessary to ensure that every entry in a vector of vectors has the same length, i.e. that a vector of vectors is a matrix. As well as detecting irregularities, it is able to detect all other shape errors, such as multiplying matrices of innapropriate sizes, or having incompatible numbers of dimensions. It is the power of shape analysis that makes poly-dimensional programming feasible. Knowledge of the shapes can be used to improve memory management during compilation of the resulting imperative program. In particular, FISh supports a clear stack discipline, and so does not require a garbage collector. The existing FISh compiler translates programs in to simple C code, which is then compiled and executed in the usual way. This approach is also being applied in the design and implementation of a parallel version of FISh, called GoldFISh. F = I + Sh ~~~~~~~~~~ The slogan is represented within the standard prelude by a function proc2fun : (var a -> var b -> comm) -> (#b -> #a) -> b -> a for converting procedures (and shapes) to functions. proc2fun pr sh x uses the shape function sh and the shape #x of the array x to determine the shape of the result. It then creates a local variable y of this shape, and invokes the procedure pr on and a stored value of x, finally returning the value of y. Semantics ~~~~~~~~~ Shape analysis is supported by a clean and powerful categorical semantics, in which the shape-data (or shape-entry) decomposition is represented by a pullback. For multi-dimensional arrays, this is entries [a] ---------> List a | | | |___| | shape | | map # | | \/ \/ List N x #a -----> List #a c where c takes the list of numbers ns and the a-shape sh and produces a list of length given by the product of ns whose entries are all sh. In other words, all entries of an array must have the same shape. Poly-dimensionality ~~~~~~~~~~~~~~~~~~~ FISh supports the usual Hindley-Milner style of polymorphism. It also supports polymorphism in array sizes (unlike earlier Algol-like languages) and in the number of dimensions of an array. That is, FISh supports polydimensional programming. For example, the map function is defined to have type map : (a -> b) -> [a] -> [b] and so may act on a vector, matrix or higher-dimensional array. However, the existence of the simple imperative features means that this can be compiled into a sequence of nested for-loops corresponding to the number of dimensions of the array argument. Polydimensionality is a form of *shape polymorphism*. Array Programming ~~~~~~~~~~~~~~~~~ Poly-dimensionality means that many array programs, e.g. numerical recipes, can be written for any number of dimensions while maintaining static type and shape checking. For example, FISh supports poly-dimensional stencilling and a poly-dimensional difference equation solver (see Sample Programs). Parallel Programming ~~~~~~~~~~~~~~~~~~~~ Size and shape are important parameters in estimating the cost of alternative parallel implementations. FISh has been designed to support a parallel variant, called GoldFISh, currently under development. GoldFISh will support additional parallel combinators for some of the existing FISh functions that express the usual second-order constants and also the usual array distributions (see Sample Programs). ***********************************

1 0

more precisely ...
by Steve Awodey 08 May '98

08 May '98

Dear Colleagues, Since this is the categories list, I could and should have been more specific about the contents of the preprint I announced yesterday: "Topological representation of the lambda-calculus", available from my page on the WWW, http://www.andrew.cmu.edu/user/awodey/ In a nut-shell, the point is that the Butz-Moerdijk spatial covering theorem for topoi can be used to embed any CCC fully and faithfully (and CC) into a topos of sheaves on a space. So the "topological semantics" mentioned are actually in such topoi of sheaves. Steve A.

1 0

ICALP'98: Call for Participation
by Uffe Henrik Engberg 08 May '98

08 May '98

CALL FOR PARTICIPATION ICALP'98 25th International Colloquium on Automata, Languages, and Programming Aalborg, Denmark July 13-17, 1998 http://www.cs.auc.dk/icalp98/ The International Colloquium on Automata, Languages, and Programming (ICALP) is the annual conference series of the European Association for Theoretical Computer Science (EATCS). It is intended to cover all important areas of theoretical computer science. During 5 conference days and two weekends, ICALP will give you the opportunity to choose between 70 regular papers, 9 invited lectures, including the GÃ¶del award lecture, and 4 thematic workshops and one associated summer school offering dozens of more talks! The deadline for early registration is May 22! Please register NOW! The final deadline for registration is June 12. The full programme and registration form are available at the web address above and from the organizers (just send a message to icalp98(a)cs.auc.dk or a fax to +45 98159889). Kim Guldstrand Larsen ICALP Conference chair BRICS Department of Computer Science Aalborg University Fredrik Bajersvej 7 9220 Aalborg DENMARK Tel.: +45 96 35 88 93 (direct)

1 0

preprint available
by Steve Awodey 07 May '98

07 May '98

Dear Colleagues, The preprint mentioned below is available from my page on the WWW, http://www.andrew.cmu.edu/user/awodey/ Please let me know if you have difficulty obtaing or printing it, or if you would like to have a paper copy sent. Steve A. ******************************************************************************* "Topological representation of the lambda-calculus" S. Awodey Abstract: The lambda-calculus can be represented topologically by assigning certain spaces to the types and certain continuous maps to the terms. Using a recent result from topos theory, the usual calculus of lambda-conversion is shown to be deductively complete with respect to such topological semantics. It is also shown to be functionally complete, in the sense that there is always a ``minimal'' topological model, in which every continuous function is lambda-definable. These results subsume earlier ones using cartesian closed categories, as well as those employing so-called Henkin and Kripke lambda-models. *******************************************************************************

1 0