July 1991 - Categories - categories.org.au

New email address
by street＠macadam.mpce.mq.edu.au 29 Jul '91

29 Jul '91

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: <street(a)macadam.mpce.mq.edu.au> Best regards, Ross

1 0

Query on Topos of Labeled Trees
by Purandar Bhaduri 19 Jul '91

19 Jul '91

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. ===================================

1 0

None
by pratt＠cs.stanford.edu 12 Jul '91

12 Jul '91

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 =========================

1 0

None
by stark＠sbcs.sunysb.edu 12 Jul '91

12 Jul '91

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 ==================================

1 0

T-Algebras in PLC
by Martin Hofmann 11 Jul '91

11 Jul '91

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. ====================================

1 0

None
by unknown＠categories.mta.ca 10 Jul '91

10 Jul '91

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(a)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(a)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(a)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(a)cs.cmu.edu ==============================

1 0

None
by jds＠rademacher.math.upenn.edu 09 Jul '91

09 Jul '91

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.... ================================

1 0