September 2001 - Categories - categories.org.au

Only two SMC structures on Cat?
by Jason C Reed 27 Jul '02

27 Jul '02

Power, A.J. and Robinson, E.P. Premonoidal categories and notions of computation (ftp://ftp.dcs.qmw.ac.uk/pub/lfp/edmundr/premoncat.ps.gz) in section 2 asserts that there is excatly one symmetric monoidal closed structure on Cat besides the cartesian one. Does anyone know [the location of] a proof? ---Jason

3 2

paperback announcement: Categorical Logic and Type Theory
by Bart Jacobs 15 Mar '02

15 Mar '02

Dear Colleague, I am happy to announce that Elsevier has now published a paperback version of my book B. Jacobs, Categorical Logic and Type Theory Studies in Logic and the Foundations of Mathematics 141, North Holland, Elsevier, 1999. 780 pages. The regular price of the paperback is NLG 150 / Euro 68.07 / US$ 74 Elsevier now offers a discount of 25% for this paperback if you order before 31 july 2001, using the attached form. In that case the price is: NLG 112.50 / Euro 51 / US$ 55.50. If you wish to use this special offer, please fill in the form, and send it in time to Andy Deelen at Elsevier (precise address at bottom of the form). Do not send it to me. The book gives a survey of categorical logic and type theory starting from the unifying concept of a fibration. Its intended audience consists of logicians, type theorists, category theorists and (theoretical) computer scientists. It contains the following chapters. Prospectus Introduction to fibred category theory Simple type theory Equational Logic First order predicate logic Higher order predicate logic The effective topos Internal category theory Polymorphic type theory Advanced fibred category theory First order dependent type theory Higher order dependent type theory References Notation index Subject index More information can be obtained from the authors webpage: http://www.cs.kun.nl/~bart/CLT/bookinfo.html Bart Jacobs, Dep. Comp. Sci., Univ. Nijmegen, P.O. Box 9010, 6500 GL Nijmegen, The Netherlands. Email: bart(a)cs.kun.nl PS. Please pass this information on to your institute's librarian.

2 1

preprint: "Ordinary and directed combinatorial homotopy,..."
by grandis＠dima.unige.it 28 Sep '01

28 Sep '01

The following paper is available in ps and ps.gz. It is about my talk at: 'Conference on Algebraic Topological Methods in Computer Science' Stanford, July 30 - August 3, 2001. 'Ordinary and directed combinatorial homotopy, applied to image analysis and concurrency' Marco Grandis Abstract. Combinatorial homotopical tools developed in previous works, and consisting essentially of intrinsic homotopy theories for simplicial complexes and directed simplicial complexes, can be applied to explore mathematical models representing images, or directed images, or concurrent processes. An image, represented by a metric space X, can be explored at a variable resolution e > 0, by equipping it with a structure t_eX of simplicial complex depending on e; this complex can be further analysed by homotopy groups \pi^e_n(X) = \pi_n(t_eX) and homology groups H^e_n(X) = H_n(t_eX). Loosely speaking, these objects detect singularities which can be captured by an n-dimensional grid, with edges bound by e; this works equally well for continuous or discrete regions of euclidean spaces. Similarly, a directed image, represented by an 'asymmetric metric space', produces a family of directed simplicial complexes f_eX and can be explored by the fundamental n-category of the latter. The same directed tools can be applied to mathematical models of concurrent automata, like Chu-spaces. AVAILABLE AT: ftp://www.dima.unige.it/Home/grandis/public/Cmb.App.ps ftp://www.dima.unige.it/Home/grandis/public/Cmb.App.ps.gz (18p, 260K) ***** With best regards Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis(a)dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/~grandis/ ftp://www.dima.unige.it/Home/grandis/public/ 1-Oct-2001 18:40:07 -0300,1032;000000000000-0000002b >From cat-dist(a)mta.ca Mon Oct 01 18:40:07 2001

1 0

Re: categories or graphs?
by S Vickers 26 Sep '01

26 Sep '01

Peter is quite right. I was mistaken in saying graph shape and category shape are mathematically equivalent. Category shape for diagrams has graph shape plus the commutativities, which graph shape on its own does not capture. His justification for considering category shape is much more profound than the ones I mentioned. Nonetheless, when verifying the conditions for cones/cocones, or for limits/colimits, the commutativities make no difference and it suffices to check on a generating graph. Thus it is worth bearing in mind that in such contexts one might correctly and more simply just use graph shape, as Gillian and I did in "Presheaves as configured specifications". (For those interested it's on the web via my home page at http://mcs.open.ac.uk/sjv22 .) Steve Vickers. 26-Sep-2001 13:27:29 -0300,2418;000000000000-00000026

3 2

Tangle, Braid... related category?
by Jules Bean 26 Sep '01

26 Sep '01

There's a category Braid, or Brd, whose objects are the natural numbers and morphisms "n parallel pieces of string twisted around each other". And a related one Tng where the objects distinguish between 'string going in' and 'string going out', and strings are allowed to double back on themselves. Related to these two these is a category whose objects are again the natural numbers, and whose morphisms are pieces of string which are allowed to split into multiple strands, and join together into single strands, such as the following morphism 3 --> 2: * * * \ / / | /\ \ / | \/ | * * (excuse the crude drawing which will only look OK if you have a monospaced font). There are various ways this category could be formulated (are the strings allowed to cross each other? are they allowed to double back? etc), but my question is: has anything been written about it? Does it have a name? Does it remind anyone of another category which has been studied? Yours, Jules Bean 20-Sep-2001 20:06:37 -0300,6821;000000000001-0000001a

5 6

Linear Monads (Was Re: Tangle, Braid... related category?)
by Robert A.G. Seely 24 Sep '01

24 Sep '01

> Jules Bean <jules(a)jellybean.co.uk> wrote: > Related to these two these is a category whose objects are again the > natural numbers, and whose morphisms are pieces of string which are > allowed to split into multiple strands, and join together into single > strands, such as the following morphism 3 --> 2: > > * * * > \ / / > | /\ > \ / | > \/ | > * * As Tom Leinster, Joachim Kock, and John Baez point out, there are a number of studies of such structures. But for a coherent general perspective, I would also point out that this is what we (Robin Cockett, J"urgen Koslowski, and Robert Seely) call a "linear monad" in a linear bicategory ("Introduction to Linear Bicategories", Math Struct in Comp Sci 10 (2000) 165--203, also available from my web site, url as given below). The general theory is worked out in section 4 of that paper. A linear bicategory may be thought of as a bicategory with two (usually distinct) horizontal composition operations (we think of them as tensors). In figures such as above, we can imagine one tensor as "tieing together" the top wires, and the other for the bottom wires. Monads and comonads may be defined in this setting, and a linear monad is a pair consisting of a monad and a comonad which are "compatible" with one another, each of which acts (or coacts, as appropriate) upon the other. As we point out in the paper, these are a natural generalization of Frobenius algebras, to pick up Joachim Kock's reference. - all the best, Robert (Seely) ================== R.A.G. Seely <rags(a)math.mcgill.ca> <http://www.math.mcgill.ca/rags> 26-Sep-2001 13:48:45 -0300,4134;000000000001-00000027

1 0

RFC Walters "Categories and Computer Science"
by Galchin Vasili 22 Sep '01

22 Sep '01

Hello, I am rereading Walters' book in particular the functor chapter. I am also reading Barr & Wells "Category Theory for Computing Science" (erd edition) ... in particular chapter 4 on diagrams, sketches, etc. In Walters' functor chapter, I am wondering whether Example 13 is totally correct. It doesn't seem to me that "A" is a graph and what is called a functor is really a graph morphism or to put it another way, Example 13 should be couched in terms of a (formal!!) diagram of shape "A". I know that somebody will respond and say that "A" is really a category with implicit identity arrows. However, my retort would be that "A" is intended to be a graph (without composition). What do others think? Regards, Bill Halchin 20-Sep-2001 19:27:30 -0300,1707;000000000000-00000019

3 3

job: PhD studentship at Sussex
by Bernhard Reus 21 Sep '01

21 Sep '01

Please pass on to interested students. Apologies for multiple copies. --------------------------------------------------------------------- A three year PhD studentship is available as part of the EPSRC project `Programming Logics for Denotations of Recursive Objects' at the School of Cognitive and Computing Sciences (COGS) at the University of Sussex at Brighton. The aim of this project is to develop a programming logic for an object-oriented language based on denotational semantics. Starting from some results already obtained for untyped languages the main task will be to derive and study reasoning principles in a _typed_ setting. LCF (Logic of Computable Functions), developped in the seventies, acts somehow as our role model. Mechanized even by a powerful theorem prover, it supports reasoning about functional programs. We plan to follow similar objectives for the object-based paradigm. Prototypical implementations of (parts of) results using a theorem prover are not the main focus of the project, but may turn out to be fruitful during the development process. Prospective candidates should have an appropriate degree in computer science or mathematics. Some background in programming logics, domain theory or type theory are useful but not essential. The studentship will cover all fees for a three year period and a yearly maintenance grant at the standard rate (currently GBP 6800). It comes with sufficient funds to cover travel to summer schools and conferences, and possibly brief visits to other institutions. A possible starting date is January 2002, but earlier or slightly later dates can be arranged. The project student will be a member of the Foundations group at COGS. This group (see also http://www.cogs.susx.ac.uk/foundations ) shares interests in all kinds of semantical questions and runs regular internal seminars and other events. It consists currently of five members of staff (Hennessy, McCusker, Rathke, Reus, Sassone), three research fellows (Harmer, Laird, Merro) and two PhD students. The group is still growing and its manageable size is considered beneficial to the internal scientific exchange. Brighton itself is a enchanting, exciting, and extraordinary seaside city. With its cosmopolitan air, feverish nightlife, abundance of culture, and vicinity to London, it is an attractive place to live and study (more info: http://www.susx.ac.uk/central/students.shtml ). For enquiries and further details please contact Bernhard Reus at bernhard(a)cogs.susx.ac.uk 23-Sep-2001 13:38:30 -0300,3835;000000000000-00000022

1 0

ICGT 2002 first announcement
by Kreowski 19 Sep '01

19 Sep '01

Dear Colleague, Please find below the first announcement of the 1st International Conference on Graph Transformation (ICGT 2002) as a simple text. Slightly more fancy versions can be found under http://www.informatik.uni-bremen.de/theorie/icgtfa.pdf http://www.informatik.uni-bremen.de/theorie/icgtflyer.pdf The latter may be printed on a single sheet of paper (front and back) and provides a 4-page flyer if folded in the middle. Please visit also the ICGT 2002 website for more detailed information: http://www.lsi.upc.es/icgt2002 . With kind regards, Andrea Corradini and Hans-Joerg Kreowski xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Please apologize if you receive multiple copies of this message. FIRST ANNOUNCEMENT ICGT 2002 1st International Conference on Graph Transformation Barcelona (Spain), October 7-12, 2002 The first international conference on graph transformation ICGT 2002 including several satellite events will be held in Barcelona in the second week of October 2002. It follows a series of six international workshops on graph transformation with applications in computer science held from 1978 to 1998 in Europe and the USA. The conference takes place under the auspices of EATCS, EASST, and IFIP WG 1.3. The proceedings of ICGT will be published by Springer-Verlag in Lecture Notes in Computer Science. Scope. Graphical structures of various kinds (like graphs, diagrams, visual sentences and others) are very useful to describe complex structures and systems in a direct and intuitive way. These structures are often augmented by formalisms which add to the static description a further dimension allowing for the modelling of the evolution of systems via any kind of transformation of such graphical structures. The field of Graph Transformation is concerned with the theory, applications and implementation issues of all these formalisms. The theory is strongly related to areas such as graph theory and graph algorithms, formal language and parsing theory, theory of concurrency and distributed systems, formal specification and verification, logic and semantics. The application areas include all those fields of Computer Science, Information Processing, Engineering and Natural Sciences where static and dynamic modeling by graphical structures and graph transformations, respectively, play an important role. In many of these areas tools based on graph transformation technology have been implemented and used. Topics of interest include, but are not limited to the following. On the more theoretical side: - General models of graph transformation - Node-, edge-, and hyperedge replacement graph grammars - Concurrency, distribution, and formal semantics - Term graph rewriting - Network computing - High-level replacement systems - Hierarchical graphs and decompositions of graphs - Logic expression of graph transformation properties - Graph theoretical properties of graph languages - Geometrical and topological aspects of graph transformation - Automata on graphs and parsing of graph languages - Analysis of graph transformation systems - Structuring and modularization concepts - Semantics of UML and other visual modelling techniques On the more applied side: - Specification languages - Implementation of programming languages - Design of visual programming environments - Massively parallel computing - Software engineering and modular systems - Development of meta CASE tools - Software architecture - Information security - Visual languages - Actor systems and Petri nets - Rule- and knowledge-based systems - Developmental systems - Pattern generation and picture processing - Pattern matching - Tool support - Graph exchange formats - Layout algorithms Invited speakers. Carlo Ghezzi (Milano, Italy) David Harel (Rehovot, Israel) Robin Milner (Cambridge, UK) Program committee. Michel Bauderon (Bordeaux, France), Paolo Bottoni (Rome, Italy), Andrea Corradini (co-chair; Pisa, Italy), Hartmut Ehrig (Berlin, Germany), Gregor Engels (Paderborn, Germany), Reiko Heckel (Paderborn, Germany), Dirk Janssens (Antwerp, Belgium), Hans-JÃ¶rg Kreowski (co-chair; Bremen, Germany), Ugo Montanari (Pisa, Italy), Manfred Nagl (Aachen, Germany), Fernando Orejas (Barcelona, Spain), Francesco Parisi-Presicce (Rome, Italy), Mauro PezzÃ© (Milano, Italy), John Pfaltz (Charlottesville, Virginia, USA), Rinus Plasmeijer (Nijmegen, The Netherlands), Detlef Plump (York, Great Britain), Azriel Rosenfeld (Maryland, USA), Grzegorz Rozenberg (Leiden, The Netherlands), Andy SchÃ¼rr (Munich, Germany), Gabriele Taentzer (Berlin, Germany), Gabriel Valiente (Barcelona, Spain) Important dates. Submission of papers: April 1, 2002 Notification of acceptance: June 1, 2002 Final version due: June 20, 2002 Main conference: October 8-11, 2002 Conference including satellite events: October 7-12, 2002 General Organizing Committee. Andrea Corradini (Pisa, Italy), Hartmut Ehrig (chair; Berlin, Germany), Hans-JÃ¶rg Kreowski (Bremen, Germany), Fernando Orejas (Barcelona, Spain), Grzegorz Rozenberg (Leiden, The Netherlands) Local Organizing Committee. Nikos Mylonakis, Fernando Orejas (chair), Elvira Pino, Gabriel Valiente Steering committee. Michel Bauderon (Bordeaux, France), Andrea Corradini (Pisa, Italy), Hartmut Ehrig (chair; Berlin, Germany), Gregor Engels (Paderborn, Germany), Dirk Janssens (Antwerp, Belgium), Hans-JÃ¶rg Kreowski (Bremen, Germany), Ugo Montanari (Pisa, Italy), Manfred Nagl (Aachen, Germany), Francesco Parisi-Presicce (Rome, Italy), John Pfaltz (Charlottesville, Virginia, USA), Rinus Plasmeijer (Nijmegen, The Netherlands), Azriel Rosenfeld (Maryland, USA), Grzegorz Rozenberg (Leiden, The Netherlands) More details concerning ICGT 2002 including the main conference, satellite events, submission of papers, local information on the conference site, and travel information can be found on the website of ICGT 2002, http://www.lsi.upc.es/icgt2002 . For further information, you may contact also Andrea Corradini (andrea(a)di.unipi.it) Hans-Joerg Kreowski (kreo(a)informatik.uni-bremen.de) or Fernando Orejas (orejas(a)lsi.upc.es) Conference address. ICGT 2002 Fernando Orejas Universitat PolitÃ¨cnica de Catalunya Departament de Llenguatges i Sistemes InformÃ tics Campus Nord - Edif. C6 08034 Barcelona, Spain Tel: +93 401 7018 Fax: +93 401 7014 Satellite events. GRA-TRA TUTORIAL Tutorial on Foundations and Applications of Graph Transformation

1 0

Union College Conference
by Susan Niefield 19 Sep '01

19 Sep '01

We hope this message finds you well, and that your family and friends are okay after last week's tragedies. We are planning to go ahead with the Union College conference on the weekend of September 29-30. A complete schedule for the conference, including talks in the parallel sessions, is now availabe at our website www.math.union.edu/~niefiels/01Conference/ If you are planning to attend, but have not yet registered or contacted us, please do so by Monday, September 24th, so that we will be able to make arrangements for the conference banquet. Thanks. 20-Sep-2001 19:26:16 -0300,1388;000000000000-00000018

1 0