Date: Tue, 9 Jul 91 11:41:38 GMT-0400 From: jds@rademacher.math.upenn.edu The following `must have' been considered already. It is possible to define homotopy groups for a simplicial set. How about for an n-category? or anyway a 2-category? Naively, the problem seems to be how to `add' 2-cells, but now that we have good pasting theorems.... ================================ Date: Tue, 9 Jul 91 10:01:50 EDT Seventh Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE June 22--25, 1992, Santa Cruz, California PRELIMINARY CALL FOR PAPERS The LICS Symposium aims for wide coverage of theoretical and practical issues in computer science that relate to logic in a broad sense, including algebraic, categorical and topological approaches. Suggested, but not exclusive, topics of interest include: abstract data types, automated deduction, concurrency, constructive mathematics, data base theory, finite model theory, knowledge representation, lambda and combinatory calculi, logical aspects of computational complexity, logics in artificial intelligence, logic programming, modal and temporal logics, program logic and semantics, rewrite rules, software specification, type systems, verification. PROGRAM CHAIR: Prof. Andre Scedrov Inst. for Research in Cognitive Sci. University of Pennsylvania 3401 Walnut Street, Suite 400C Philadelphia, PA 19104-6228 USA lics92@cis.upenn.edu FAX (215) 573 2048 (Attn: LICS) PROGRAM COMMITTEE: E. B"orger, U. Pisa; R. Cleaveland, North Carolina State; S. Cook, U. Toronto; N. Dershowitz, U. Illinois; J.-Y. Girard, U. Paris 7; R. van Glabbeek, Stanford; S. Hayashi, Ryukoku U.; J. Hughes, U. Glasgow; N. Jones, U. Copenhagen; J.-L. Lassez, IBM Watson; E. Moggi, U. Genoa; A. Nerode, Cornell U.; F. Pereira, AT&T Bell Labs; A. Scedrov (Chair), U. Pennsylvania; D. Scott, CMU; A. Tarlecki, Inst. C.S., PAN Warsaw; M. Vardi, IBM Almaden. CONFERENCE CHAIR: GENERAL CHAIR: Prof. Phokion Kolaitis Prof. Albert R. Meyer Computer and Information Sciences MIT Lab. for Computer Sc Univ. of California, Santa Cruz NE43-315 Santa Cruz, CA 95064 USA 545 Technology Square kolaitis@saturn.ucsc.edu Cambridge, MA 02139 USA PAPER SUBMISSION: Seven (7) hard copies of a detailed abstract -- not a full paper -- should be RECEIVED by DECEMBER 9, 1991 by the Program Chair (Attn: LICS). In addition, an electronic version of the cover page in plain ASCII format should be received at lics92@cis.upenn.edu, also by December 9, 1991. Authors without access to email should send a hard copy of the cover page. Authors without access to reproduction facilities may submit a single copy of their abstract. Authors will be NOTIFIED of acceptance or rejection by FEBRUARY 3, 1992. Accepted papers in the specified format for the symposium proceedings will be due APRIL 7, 1992. The COVER PAGE of the submission should include the title, authors, a brief synopsis, and the corresponding author's name, address, phone number, FAX number, and email address if available. Abstracts must be in English, clearly written, and provide sufficient detail to allow the program committee to assess the merits of the paper. References and comparisons with related work should be included. Abstracts of fewer than 1500 words are rarely adequate, but the total abstract, including references, should not exceed 4000 WORDS. The results must be unpublished and not submitted for publication elsewhere, including proceedings of other symposia or workshops. Late abstracts, or those departing significantly from these guidelines, run a high risk of rejection. The symposium is sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with the Association for Symbolic Logic and the European Association of Theoretical Computer Science. ORGANIZING COMMITTEE: M. Abadi, J. Barwise, M. Blum, A. Chandra, R. Constable (Chair Elect), E. Engeler, J. Gallier, J. Goguen, Y. Gurevich, S. Hayashi, D. Johnson, G. Kahn, J.W. Klop, P. Kolaitis, D. Kozen, D. Leivant, Z. Manna, A. Meyer (Chair), G. Mints, J. Mitchell, Y. Moschovakis, R. Parikh, G. Plotkin, G. Rozenberg, A. Scedrov, D. Scott, J. Tiuryn, R. de Vrijer For further announcements, contact the PUBLICITY CHAIR: Prof. Daniel Leivant School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA lics@cs.cmu.edu ============================== From: mas010@vaxa.bangor.ac.uk Date: 11 July, 1991 In the groupoid case, there are various possibilities for `higher dimensional objects', namely crossed complexes, infinity-groupoids, omega-groupoids, simplicial T-complexes, poly-T-complexes (see the references in my article on `Some problems in non-abelian homological and homotopical algebra' SLNM 1418, ed M Mimura). Crossed complexes are useful because of their close relations to classical tools (chain complexes, universal covering spaces, relative homotopy groups). Omega-groupoids (=cubical infinity-groupoids with connections, and so thin structures) are useful because of the clear compositions, monoidal closed structures, and context for proving the generalised Van Kampen Theorem. Simplicial T-complexes are useful because of the relation with classical simplicial techniques, and because of a lingering suspicion in some quarters that it is old fashioned to use cubical sets. The aim of the poly-theory was to to give a context for group theory methods such as Van Kampen diagrams (see D.Johnson, Presentations of groups, LMS Lecture notes). In any case, what is wrong with pentagons, or rhombic dodecahedra? How do Stasheff polyhedra fit into a general theory similar to simplicial sets? What algebraic structures do Stasheff T-complexes correspond to? What is not so clear is what are the valuable features of infinity-groupoids. It is somehow interesting to know they are there, but what does one do with them when one has got them? I wish I knew. For example, translating the monoidal closed structure on omega-groupoids to the infinity-groupoid case, with explicit formulae, seems a formidable task. (It is not so good for the simplicial case, either!) There are also problems. For example, what is the crossed complex corresponding to the free infinity-groupoid on one generator of dimension n? It should be the fundamental crossed complex of the n-cell with its globular (hemi-spherical ) subdivision. But how does one prove this? The corresponding results for the cubical and simplicial case use basic facts on the homotopy theory of geometric realisations for the (current) proofs. A paper of Spencer and Wong (CTGD 24 (1983) 164-192) shows the advantage of working with double categories with thin structure rather than with 2-categories. Part of the aim of the thesis of F. Al-Agl was to get similar methods in the n-dimensional case. Intuitively, one hopes to replace pasting arguments by calculations with thin elements, since these obey the transparent rule: any composition of thin elements is thin. One can also make inductive arguments about how degenerate is a thin element (see Proposition 4.4 of Brown-Higgins JPAA 22 (1981) 11-41: the whole theory of omega-groupoids is designed to make this Proposition work, since the immediately following lemma gives the crucial result that certain choices previously made do not affect the final composition, and this is proved by showing that an (n+1)- dimensional cube is degenerate in direction n+1, so that its two opposite faces in this direction are the same). Trying to do this last proof of the Van Kampen Theorem in infinity-groupoids is a nightmare of intricately coiling tubes (see Whitney's tube systems?), so that the work with Loday on cat-n-groups adopted an entirely different approach, using sophisticated simplicial techniques, which in some mysterious way accommodate all these local problems. Clearly n-categories arise in nature. But it would seem useful to assess the advantages and disadvantages of the various possible categories in which to work before committing oneself to setting up a homotopy theory in one setting rather than another. The advantage of having these (highly non-trivial) equivalences of categories is that one can swap round at will, not noticing the technical nature of the machine which allows one to do this. But as Vaughan Pratt emphasised, there is still the problem of proving that infinity-categories are equivalent to omega-categories (=cubical infinity-categories with connections), and this is not yet solved by the work of Al-Agl/Steiner, although that does give a beautiful cubical setting equivalent to infinity-categories. I was very interested to see the high priority given by Vaughan to this question. Ross Street in an extra informal lecture at Montreal explained the background in constructing `cohomology with coefficients in an n-category' for his work on nerves of infinity-categories (following up suggestions of John Roberts). I have tended to concentrate on the corresponding possibilities for the groupoid case, but work of Pachkoria explained at Montreal shows the geometric possibilities of cohomology with coefficients in a commutative monoid. Recent work of Larry Breen gives Schreier systems with coefficients in a crossed square, while Bullejos and Cegarra have considered coefficients in a reduced `crossed module of length 2' (a la Conduche). Brown-Higgins deal in a recent preprint (`The classifying space of a crossed complex', MPCamb Phil Soc, in press) with coefficients in a crossed complex. It all looks very promising. Ronnie Brown =================================== Date: Thu, 11 Jul 91 14:17:03 -0400 From: stark@sbcs.sunysb.edu (Eugene Stark) Carboni and Walters (Cartesian bicategories I, JPAA 49(1987), p 13) state: "Consider a bicategory B with a tensor product. Then the tensor product is the biproduct iff every object has a cocommutative comonoid structure and every arrow is a comonoid homomorphism." Presumably this fact should specialize to the case of symmetric strict monoidal categories, so that for a symmetric strict monoidal category C, the tensor product is the cartesian product iff every object has a cocommutative comonoid structure and every arrow is a comonoid homomorphism. Let C be a symmetric strict monoidal category, with identity object I, tensor product denoted by *, and with symmetry isomorphisms sXY: X*Y --> Y*X. Suppose each object X in C has a cocommutative comonoid structure given by the arrows: tX: X --> I dX: X --> X*X The comonoid equations are (dropping the names of the objects for simplicity): (1*t)d = 1 (counit) (t*1)d = 1 (d*1)d = (1*d)d (coassociativity) sd = d (cocommutativity) Suppose further that every arrow of C is a comonoid homomorphism. It should then follow that the tensor product is the cartesian product. Presumably the projections would be (1*t): X*Y-->X and (t*1): X*Y-->Y, and the target tupling of f: Z-->X and g: Z-->Y would be given by (f*g)d. The equations that would have to be satisfied are: (1X*tY)(f*g)dZ = f (tX*1Y)(f*g)dZ = g (((1X*tY)h)*((tX*1Y)h))dZ = h The first two are easy to prove. Can someone tell me how to prove the third? I am probably missing something simple, but I spent a few hours on it and I just don't see it. I can reduce it to the problem of establishing either ((1X*tY)*(tX*1Y))d = 1 or else d(X*Y) = (1X * sXY * 1Y)(dX * dY) but I don't see how to prove either of these from the stated assumptions. - Gene Stark ================================== Date: 11 Jul 91 14:03:34 PDT (Thu) From: pratt@cs.stanford.edu As I'm sure someone else will say in more detail than I'm qualified to, your question is currently of considerable interest to n-category theorists (Ross Street and Mike Johnson in particular), topologists (Ronnie Brown, Richard Steiner, F. Al-Agl), and at least one computer scientist, namely myself in connection with modeling concurrent computation. A (the?) central question is whether omega-categories (Brown's terminology) (based on either simplexes or cubes) are equivalent to infinity-categories (based on n-cells) or just a special case. For myself, I'm very interested in applying homotopy *monoids* to improving on our the existing notion of computation as a path, generalizing it to a homotopy class. My paper "Modeling Concurrency with Geometry" (available by anonymous ftp as pub/cg.{tex,dvi} from boole.stanford.edu, see pub/README for abstracts of related work) defines a concurrent automaton with n concurrent processes to be an n-category, and (elsewhere in the paper) suggests the notion of monoidal homotopy without giving a knock-down definition of it, and contrasts it with group homotopy. Since then Rob van Glabbeek has encouraged me to look at neither simplicial sets nor n-categories but rather cubical sets. For now these seem somewhat more tractable than n-categories for modeling concurrency, and better capture the essence of concurrent automata. n-categories seem just a bit too general. However I'm still quite open-minded about this since I don't see really persuasive arguments for either. Vaughan Pratt ========================= Subj: T-Algebras in PLC Date: Thu, 11 Jul 91 14:46:56 +0200 From: Martin Hofmann During the lecture of Bainbridge,Freyd Scedrov,Scott's-paper "Functorial Polymorphism" (TCS 90) the following questions arose: \item Does the authors' construction of an interpretation of PLC d efinitely imply that there is a categorical PLC-model in the sense of Reynolds in which $\forall \alpha.(T(\alpha)->\alpha)->\alpha$ is interpreted as the initial T-Algebra? \item Does this model (if there is one) have an object with two distinguishable points, or equivalently is true <> false ? \item Does the model construction described extend to a model of the Calculus of Constructions or even ECC, so that we could consistently add an axiom claiming the initiality of $\forall \alpha.(T(\alpha)->\alpha)->\alpha$ using Leibniz's equality (And $not (true = false)$ of course)? Could anyone -- perhaps the authors themselves -- help me to get answers to these problems? -- Martin Hofmann P.S. I'm a grad-student working on verification of ML-programs with ECC and I've represented ML's datatypes using the above quoted T-algebra-expression. ==================================== Subj: Query on Topos of Labeled Trees Date: Thu, 18 Jul 91 12:05:30 -0700 From: Purandar Bhaduri I am a graduate student working in the area of categorical models of process behavior. One of the models I am looking at is the topos of labeled trees (cf. Enriched Categorical Semantics for Distributed Calculi, S.Kasangian and A.Labella, to appear in Jn. of Pure and Algebra). In this paper and elsewhere there are references to unpublished manuscripts of Benabou, which are difficult to get hold of. My question is regarding the subobject classifier in this topos of labeled trees : What does it look like, for a given set of labels A? Also, are there any published works on the topos of labeled trees where its properties are spelled out in detail? Any help will be greatly appreciated. Sincerely, Purandar Bhaduri. =================================== Subj: New email address Date: Mon, 29 Jul 91 15:22:16 +1000 From: street@macadam.mpce.mq.edu.au (Ross Street) Dear Bob, The problem with my email has been resolved. The old address will still work but is being phased out. Please advise your bulletin board subscribers that my new address is: Best regards, Ross