May 1998 - Categories - categories.org.au

Evolutive systems with memory
by Matthieu Amiguet 28 May '98

28 May '98

Hello! I'm trying to get information about Ehresmann & Vanbremeersch theory of "Evolutive systems with memory". This is a theory for modelling complex evolutive systems using category theory. I've got a couple of papers (from 1989 to 1992), but I would like to find a synthtic article which could present the matter more consistently... Does anybody know if there is such a thing, or at least whom I could ask? Thank you for any help, Matthieu Amiguet UniversitÃ© de Neuchatel CH-2000 Neuchatel

1 0

Regular embedding
by Michael Barr 27 May '98

27 May '98

A month or so ago, I got a note from Ross Street asking about my 1986 JPAA paper on representations of categories. The main point of that paper was to give a new, relatively simple proof of the full embedding theorem for regular categories. Unfortunately, I tried to get too general and got tangled in the variance, so that the argument could not be followed. Follows is my final note to Ross. The argument is really quite simple and can be described as follows: 1. Show that when @C (read script C) is regular, so is Lex(@C,Set)\op. (Lex=FL is the finite limit preserving functors. This result is really the only new thing in the paper.) 2. Adapt Grothendieck's transfinite induction proof of the existence of injectives in an AB5 abelian category to show that Lex(@C,Set)\op has enough @C-projectives = regular functors. 3. Adapt Mitchell's proof of the abelian category full embedding theorem to show that by taking a sufficiently large full subcategory @P in Lex(@C,Set) consisting of regular functors, then the evaluation functor @C --> Func(@P\op,Set) is full and faithful. That's all there is to it. I plan to post on triples in the next few days a revised version of the paper (it was, fortunately, one of the very first that was typed on a computer, so this is not too onerous). I will call it embedding.rev. Ross further raised the question as to whether a transfinite induction was too sophisticated for the classroom. I don't know exactly what level his course was, but I will say that if we never do a hard theorem, then the students will come away with the idea that there is no depth to category theory, an impression his colleagues will be only too happy to affirm. This argument of Grothendieck's is, after all, the first example that there could be deep results in categories. Michael ===================================================================== Dear Ross: I did not really try to understand my paper. I suspect it is a matter of trying to be too abstract and getting tangled in my own feet. At any rate, here is how I would do it for a class. First, since you didn't ask, I assume that you are happy with the fact that given a small category @C (think of that as script C; BTW, I never noticed how dreadful JPAA's scripts were), the category @L = Lex(@C,Set)\op has the property that given any functor F, there is a regular epi P -->> F such that P is projective with respect to regular epis in @C. Now consider a small full subcategory @P built out of choosing @C projective covers for each representable and a @C-projective cover for the kernel pair of each of the @C-projective covers of representables. Thus, for each object C, there is a parallel pair Q ===> P in @P, whose coequalizer in @L is C. Notice that Hom_{@L}(P,C) = PC, using Yoneda and taking the variance into account. There is an obvious functor F: @C --> Fun(@P\op,Set) that takes C to the functor P |--> Hom(P,C) = PC. This functor is clearly faithful, preserves finite limits and regular epis. The only question is the fullness. So suppose a: FC --> FB is a natural transformation. What naturality means is that for any d: Q --> P in @P, the square Hom(d,C) Hom(P,C) ----------> Hom(Q,C) | | | | aP | | aQ | | | | v v Hom(P,B) ----------> Hom(Q,B) Hom(d,B) commutes. Applied to an f: P --> C, this means that aQ(d.f) = d.aP(f). Apply this in the case that f is a coequalizer in @L to a parallel pair d,e : Q ===> P in @P. It says that aP(f).d = aQ(f.d) = aQ(f.e) = aQ(f).e and that means that there is a unique b: C --> B such that aP(f) = b.f. You finish the argument by observing that for any object R of @P and any c: R --> C, there is a lifting to an arrow g: R --> P and then aR(c) = aR(f.g) = aP(f).g = b.f.g = b.c.

4 5

ICALP'98: 2nd Call for Participation
by Uffe Henrik Engberg 26 May '98

26 May '98

---------------------------------------------------------------------- If you have already registered for ICALP98 please ignore this message! ---------------------------------------------------------------------- SECOND CALL FOR PARTICIPATION EXTENDED EARLY REGISTRATION: June 1st and NEW SPECIAL STUDENT REGISTRATION FEE 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! Due to a recent General Strike in Denmark the ICALP booklet has been delayed. Therefore we extend the deadline for early registration to JUNE 1st The final deadline for registration is still June 12. Upon numerous requests student may now register at a special low fee (DKK 1200 before June 1 and DKK 1400 after). The fee will cover conference attendance, refreshments and lunches only. Proceedings and banquet tickets can be purchased separately on arrival. Students who have already registered at the regular fee may choose on arrival to receive a refund. 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

None
by ralphw＠math.uiuc.edu 24 May '98

24 May '98

On pages 29--30 of "Categories for the Working Mathematician," MacLane reveals that "the discovery of ideas as general as [categories, functors and natural transformations] is chiefly the willingness to make a brash or speculative abstraction, in this case supported by the pleasure of purloining words from the philosophers: `Category' from Aristotle and Kant, `Functor' from Carnap and `natural transformation' from then current informal parlance." Ideas from writings of Karl Marx are described in "Conceptual Mathematics: A First Introduction to Category Theory," by Lawvere and Schanuel and elsewhere. What orientation or program of study has philosophy given the investigation of mathematical categories? Where could one begin reading to understand this influence? Was selection of "monad" influenced by writings of Leibniz? Thank you for your time. Sincerely, Ralph Wojtowicz

1 0

"Practical Foundations of Mathematics"
by Paul Taylor 23 May '98

23 May '98

Practical Foundations of Mathematics, ISBN 0-521-63107-6 To be published by Cambridge University Press, as number 59 in their series Cambridge Studies in Advanced Mathematics (which includes books by Peter Johnstone and by Jim Lambek and Phil Scott). Please see http://www.dcs.qmw.ac.uk/~pt/book/index.html for details. This is the LAST CALL FOR COMMENTS. The text is already in the hands of the copy editor for the second time. CUP hopes to have it published in time for the International Congress of Mathematicians in Berlin in August, which means I have to finish it by the end of May. I am aware that my policy of only giving away single chapters has annoyed people a bit, but it has been successful in its objective of getting attention for the whole book. (The most assiduous reader of "Proofs and Types" got to chapter 12 out of 15). I don't intend to distribute any more chapters now, though if I owe you a copy of the whole draft because you sent me comments on a chapter, please ask (tearing apart sections 1.1 and 1.2 does not count). If you have a copy of part of the book and have noticed a mis-conception, please SPEAK NOW OR FOREVER HOLD YOUR PEACE. There is really no point in telling me about missing commas in any but the most recent versions (ie 1998) as other readers, the copy editor and I have been through the text several times since I last distributed copies (in July 1997). When I am rid of the book itself, I intend to set up a web site as a repository for citations, discussion, answers to exercises and, inevitably, corrections. With the permission of the people concerned, I intend to publish some of the correspondence I have had about the book in this way, and there will be automatic facilities for readers to add further comments. Therefore any comments you have about the book which are too late for publication or which are not suitable for inclusion will not be wasted. I would like thank Pierre Ageron, Lars Birkedal, Luca Cattani, Michel Chaudron, Thierry Coquand, Robert Dawson, Luis Dominguez, Peter Dybjer, Susan Eisenbach, Fabio Gadducci, Gillian Hill, Martin Hyland, Samin Ishtiaq, Achim Jung, Stefan Kahrs, J\"urgen Koslowski, Steve Lack, Jim Lambek, Charles Matthews, Paddy Mccrudden, James Molony, Edmund Robinson, Pino Rosolini, Martin Sadler, Alan Sexton, Thomas Streicher, Charles Wells, Graham White, Andrew Wilson and Todd Wilson for taking the trouble to read parts of the draft and giving their detailed comments on it. (Please tell me if you think you should be on this list but aren't.) Paul Taylor

1 0

CONCUR '98: ACCEPTED PAPERS (and general infos)
by Davide Sangiorgi 20 May '98

20 May '98

CONCUR'98 9th International Conference on Concurrency Theory Nice, France, September 8-11, 1998 <http://www.inria.fr/concur98/> ******************************************************************* Please find below the list of PAPERS ACCEPTED at CONCUR 98, and other information including INVITED SPEAKERS and TUTORIALS, SATELLITE EVENTS, VENUE, and SOCIAL PROGRAMME. ******************************************************************** List of Accepted Papers (ordered by submission number) ~~~~~~~~~~~~~~~~~~~~~~~ Deriving unbounded Petri nets from formal languages by Philippe Darondeau Synthesis of ENI-systems Using Minimal Regions by Marta Pietkiewicz-Koutny Unfolding and Finite Prefix for Nets with Read Arcs by W. Fogler, A. Semenov, A. Yakovlev Reduction in TLA by Ernie Cohen, Leslie Lamport Herbrand Automata for Hardware Verification by W. Damm, A. Pnueli, S. Ruah Asynchronous and asynchronous cellular automata for pomsets by Dietrich Kuske A categorical axiomatics for bisimulation by Gian Luca Cattani, John Power, Glynn Winskel Priority and Maximal Progress are completely axiomatisable by Holger Hermanns, Markus Lohrey Modelling IP Mobility by Roberto M. Amadio, Sanjiva Prasad Synthesis from Knowledge-Based Specifications by Ron van der Meyden, Moshe Y. Vardi Stochastic Transition Systems by Luca de Alfaro Minimality and Separation Results on Asynchronous Mobile Processes: representability theorem by concurrent combinators by Nobuko Yoshida Reasoning about asynchronous communication in dynamically evolving object structures. by F.S. de Boer >>From Rewrite Rules to Bisimulation Congruences by Peter Sewell Detecting Deadlocks in Concurrent Systems by Lisbeth Fajstrup, Eric Goubault, Martin Raussen The Tau-Laws of Fusion by Joachim Parrow, Bjorn Victor Algebraic techniques for timed systems by A. Benveniste, C. Jard, S. Gaubert Control Flow Analysis for the pi-calculus by Chiara Bodei, Pierpaolo Degano, Flemming Nielson, Hanne Riis Nielson Simulation is Decidable for One-counter Nets by Parosh Aziz Abdulla, Karlis Cerans Fibrational Semantics of Dataflow Networks by Eugene W. Stark >>From Higher-Order pi-Calculus to pi-Calculus in the Presence of Static Operators by Jose-Luis Vivas, Mads Dam Axioms for Real-Time Logics by Jean-Francois Raskin, Pierre-Yves Schobbens, Tom Henzinger Unfold/Fold Transformations of CCP programs by Sandro Etalle, Maurizio Gabbrielli, Maria Chiara Meo A Relational Model of Non-Deterministic Dataflow by Thomas Hildebrandt, Prakash Panangaden, Glynn Winskel Decompositions of Asynchronous Systems by Remi Morin Controlled Timed Automata by Francois Demichelis, Wieslaw Zielonka Abstract games for infinite-state processes by Perdita Stevens Alternating Simulation by R. Alur, T. Henzinger, O. Kupferman On Discretization of Delays in Timed Automata and Digital Circuits by Eugene Asarin, Oded Maler, Amir Pnueli Partial Order Reductions for Timed Systems by Johan Bengtsson, Bengt Jonsson, Johan Lilius, Wang Yi Controllers for Discrete Event Systems via Morphisms by P Madhusudan, P S Thiagarajan The Regular Viewpoint on PA-Processes by D. Lugiez, Ph. Schnoebelen Probabilistic Resource Failures in Real-Time Process Algebra by Anna Philippou, Oleg Sokolsky, Insup Lee, Rance Cleaveland, and Scott Smolka Possible Worlds for process algebras by Simone Veglioni, Rocco de Nicola Towards Performance Evaluation with General Distributions in Process Algebras by Mario Bravetti, Marco Bernardo, Roberto Gorrieri Invited Speakers and Tutorials: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (in square brackets, the topic of the talk) Invited Speakers: T. Henzinger (University of California at Berkeley, USA) [Hybrid systems]; U. Herzog (Erlangen, Germany) [Process algebra for performance evaluation]; J. Rutten (CWI, Netherlands) [Coalgebraic models of computation]; J.-B. Stefani (CNET, France Telecom) [Open distributed systems]; M. Vardi (Rice University, USA) [Branching and linear time temporal logics]. Invited Tutorials : G. Berry (CMA Ecole des Mines, France) [Synchronous reactive programming and Esterel]; J.F. Groote (CWI, Netherlands) [Theorem provers in concurrency]; B. Pierce (Indiana U., USA) [Types in concurrency]. Satellite events ~~~~~~~~~~~~~~~~~ COTIC'98: 2nd international workshop on Concurrent Constraint Programming for Time Critical Applications EXPRESS'98: 5th international workshop on Expressiveness in Concurrency HLCL'98: 3rd international workshop on High-Level Concurrent Languages PAPM'98: 6th international workshop on Process Algebra and Performance Modeling CONFER W.G.: 4th workshop of the CONFER (Concurrency and Functions: Evaluation and Reduction) working group. Watch out: Submission deadlines for COTIC'98, EXPRESS'98, HLCL'98, PAPM'98 are coming up! Participation to COTIC'98, EXPRESS'98 and HLCL'98 will require no fees; PAPM will require a (low) fee; participation to CONFER is by invitation. Venue and local arrangements ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Nice is ideally located on the French Riviera. September is still very pleasant, while less crowded than the high season. Nice's international airport is well-connected to all major european and non-european cities. The conference will be held at the auditorium of Nice Museum of Modern and Contemporary Art, which is conveniently located in the heart of Nice, between the city center and the old town, and 20 minutes walk to the beach. The Museum is next to the Hotel Novotel, where tutorials, satellite workshops, and registration will be held. Social programme (to be confirmed) ~~~~~~~~~~~~~~~~ - cocktail offered by the City of Nice at the Modern Art Museum Cafe. - excursion at Cap Ferrat on Thursday 10. Cap Ferrat is a beautiful promontory between Nice and Monaco. Its attractions include: walks with spectacular views of the coast, beaches, Villa Kerylos (a copy of a sumptuous antique Greek house), Ephrussi de Rothchild Foundation, the charming villages of St-Jean-Cap-Ferrat and Beaulieu-sur-Mer. - banquet on Thursday 10 (evening) at the Royal Riviera Hotel of St-Jean-Cap-Ferrat (one of the coast's most stylish establishments). Registration and hotel information ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Both the hotel and the registration information will be available from June 8th at the CONCUR web page. ============================= For further information, check URL <http://www.inria.fr/concur98/>, or mail to concur98(a)sophia.inria.fr.

1 0

question about omega-category
by gaucher＠irma.u-strasbg.fr 20 May '98

20 May '98

Dear categorician (or categorist, I do not know the word in English), I posted the following question some days ago in sci.math.research. Maybe this list is more appropirated : I would need to understand a proof of the following proposition : There is only one functor up to isomorphism TENS : omega-Cat x omega-Cat -> omega-Cat for which C TENS - and - TENS C have right adjoint for every omega-category C and which satisfies I^p TENS I^q = I^{p+q} where I^p is the omega-category canonically associated to the p-cube, (using for example the set of composable sub pasting schemes of the pasting scheme associated to the p-cube). I have a paper from Crans ("Pasting schemes for the monoidal biclosed structure on omega-Cat") which proves explicitely the proposition. I do not understand the construction, which is very technical (*). Is there a less complicated way to prove this proposition ? I do not need an explicit construction. Any help is welcome. pg. (*) What is a pasting presentation for example ? I know the definition of pasting scheme, realization of pasting schemes, but I do not know the one of "pasting presentation". Another question : if f, g are morphisms in C and h, k morphisms in D, is there in C TENS D elements corresponding to f TENS h and g TENS k, and if the answer is yes, is it true that (f TENS h) o_p (g TENS k) = (f o_p g) TENS (h o_p k) ? I suppose that it is false : if it should be true, why the construction of this monoidal structure is so complicated ?

2 1

Who said: General Abstract Nonsense
by pareigis＠math02.mathematik.uni-muenchen.de 20 May '98

20 May '98

Hi - who coined the expression General Abstract Nonsense as a synonym for category theory? Where did it first appear in print? Thanks for any comments. Bodo -------------------------------------------------------------------- Prof. Dr. Bodo Pareigis Dept.of Mathematics, University of Munich Theresienstr. 39, D-80333 Muenchen, GERMANY ........................................... Email: pareigis(a)rz.mathematik.uni-muenchen.de Web: http://www.mathematik.uni-muenchen.de/~pareigis phone: office: +49 89-2394-4426

4 3

Nonsense
by John Duskin 20 May '98

20 May '98

It might be amusing for people to see the full context as I replied to Bodo: Serge Lang used it in his Addiison-Wesley text: " Algebra" in the first(?) 1965 edition. On page 105 after the chapter on Homology, the following appears: "EXERCISES: Take any book on homological algebra, and prove all the theorems without looking at the proofs given in that book. Homological algebra was invented by Eilenberg-Mac Lane. General category theory (i.e. the theory of arrow-theoretic results ) is generally known as <italic>abstract nonsense</italic> ( the terminology is due to Steenrod)."

1 0

abstract algebraic geometry
by Zhaohua Luo 20 May '98

20 May '98

Last year I posted the following research notes on categorical geometry: Abstract algebraic geometry (10/16/97) The language of analytic categories (three parts, 11/4/97, 11/20/97, and 12/20/97) to this list. Recently I started a small page at my home page address: www.iswest.com/~zack which, at present, only contains the slightly modified version (html files) of these notes. The paper "categorical geometry" are still under preparation, and I hope the first three chapters will be available soon. Thanks to all those who showed interests in this project. Zack Luo

3 3