From rrosebru@mta.ca Sat Jan 1 14:56:55 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA00373 for categories-list; Sat, 1 Jan 2000 13:42:59 -0400 (AST) X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs Date: Sat, 1 Jan 2000 11:48:43 -0500 (EST) From: Michael Barr X-Sender: barr@triples.math.mcgill.ca To: Categories list Subject: categories: banach operations Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Peter's last posting reminded me of something that may or may not be relevant. Sometime in the previous millennium (actually, around 3 decades ago) John Isbell made an observation that amounted to the statment that the equational theory of the unit ball functor of banach spaces (which has many more algebras than banach spaces) could be described by negation and an aleph_0-ary operation that takes {x_i} to \sum_{i=1}^\infty 2^{-i}x_i (and appropriate equations). Now a midpoint algebra with involution, as described by Peter, has all such finitary sums and if you also assume it complete, I think it is likely exactly a model of the banach space theory. Michael From rrosebru@mta.ca Sat Jan 1 14:58:30 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA32749 for categories-list; Sat, 1 Jan 2000 13:41:17 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Subject: categories: Real interval halving To: categories@mta.ca Date: Sat, 1 Jan 100 11:37:15 +0000 (GMT) X-Mailer: ELM [version 2.4 PL25] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-Id: From: "Dr. P.T. Johnstone" Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Apologies for going off at a tangent, but someone ought to pick up Vaughan's throwaway remark that the `Conway' coalgebra structure on [-\infty,\infty] is the unique `natural' structure that makes it a final coalgebra. There is another one, which was (implicitly) pointed out by Simon Norton around the time (early 1970s) when Conway was developing the theory of surreal numbers. Conway's definition is based on the idea that the simplest number between 0 and 1/2 is 1/4, the simplest between 1/4 and 1/2 is 3/8, and so on; thus the simplest number in any nontrivial interval is always a dyadic rational (i.e. one whose denominator is a power of 2). Suppose you want to regard all rationals as simple, and use smallness of denominator as a measure of simplicity; then you would say that the simplest number between 0 and 1/2 is 1/3, the simplest between 1/3 and 1/2 is 2/5, .... Norton observed that this notion of simplicity can be encoded by the notion of continued fraction, as follows: Define a bijection f: [0,1] --> [0,1] as follows: if x has binary expansion .00...011...100...011...1..., where there are a (\geq 0) zeros in the first block, then a block of b (\geq 1) 1's, then c (\geq 1) zeros, and so on, then f(x) is the continued fraction 1 -------------------- (a+1) + 1 ------------ b + 1 --------- c + ...... Thus, for example, if x = 1/4, its two binary expansions .0100000... and .00111111... yield the two expressions 1 1 -------------- and ---------- 2 + 1 3 + 1 ---------- ------ 1 + 1 \infty ------ \infty for f(1/4) = 1/3. Extend f to a function R --> R by invariance under integer translations, i.e. f(x + n) = f(x) + n if n is an integer (and set f(\infty) = \infty, f(-\infty) = -\infty, if you insist). Then if x is the Conway-simplest number in the interval (a,b), f(x) is the Norton-simplest number in (f(a),f(b)). Similarly, one can conjugate the `Conway' coalgebra structure on [-\infty,\infty] by the function f, to obtain a different (but isomorphic, and hence also final) coalgebra structure which has an explicit definition in terms of operations on continued fractions. I believe the function f appears in `Winning Ways' (I don't have my copy to hand) in the context of a game called `Contorted Fractions' (`contorted' is of course a Conwayesque conflation of `continued' and `Norton'). There are many mysteries about it. It obviously maps the dyadic rationals bijectively to the set of all rationals (and the non-dyadic rationals to the quadratic irrationals); it is strictly increasing, but it's not hard to see that its inverse is differentiable at every rational with derivative zero. Whether it's differentiable anywhere else is, I believe, an open problem (though there are certainly points where it's not differentiable). If you sketch its graph, you will see that (as well as fixing all half-integers) it has a fixed point in the interval (0,1/2) -- it's somewhere around 0.42, in decimal notation -- but we never managed to prove that this fixed point was unique, let alone determine whether it is algebraic or transcendental. Happy New Year, Peter Johnstone From rrosebru@mta.ca Sun Jan 2 11:17:44 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA01538 for categories-list; Sun, 2 Jan 2000 10:15:12 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001012203.OAA16605@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Real interval halving In-reply-to: Your message of "Sat, 01 Jan 0100 11:37:15 GMT." Date: Sat, 01 Jan 2000 14:03:53 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Thanks, Peter. One of these days I'll learn to stop sending email after midnight. Continued fractions provide equally good coalgebraic structure for both our product-with-omega functor (it's one of the examples in our paper) and Peter F.'s X v X functor. Either midnight madness or sheer forgetfulness must have possessed me to malign its applicability to the latter. While I have that excuse handy let me also repair my description (in the same message) of halving nonzero reals as right-shifting with sign extension: following the shift the second bit must then be complemented. Thus + (1/2) halves to +- (1/2 - 1/4 = 1/4) while +++ (1/2 + 1/4 + 1/8 = 7/8) halves to +-++ (1/2 - 1/4 + 1/8 + 1/16 = 7/16). In the special case of 1 as ++++... forever, +-+++... equals + (1/2), and dually for -1. Contorted fractions make an earlier appearance in Conway's On Numbers and Games (1976) (Winning Ways is 1983). I hadn't realized Norton was involved there: Conway credits several things to Norton in ONAG but I guess he must have forgotten that one. At the risk of turning this thread into a complete tangent space, yet another construction of the group of reals is as the quotient G/H of the pointwise-additive group G of bounded integer sequences by the subgroup H consisting of those sequences b of the form b_0 = a_0, b_{i+1} = a_{i+1} - 2a_i for some a in G. This definition, which avoids detouring through the rationals, resulted from my mulling over a talk at MIT by Gian-Carlo Rota in the early 1970's on representing reals as sequences of bits. I mentioned it at a recent theory lunch talk and Don Knuth mulled it over and came up with the idea of modifying the boundedness condition to allow G to be a ring thus making G/H a field (as an alternative to taking product to be the unique bilinear operation * satisfying 1*1 = 1), see Problem 10689, American Mathematical Monthly, 105(1998), p.769. I would love to know whether this construction can exploited in a coalgebraic setting. Vaughan Pratt From rrosebru@mta.ca Sun Jan 2 11:18:21 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA10336 for categories-list; Sun, 2 Jan 2000 10:14:30 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sat, 1 Jan 2000 16:53:31 -0500 From: "P. Scott" Message-Id: <200001012153.QAA11060@matrix.cc.uottawa.ca> To: categories@mta.ca Subject: categories: Re: banach operations Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Re Mike Barr's comments on Isbell's construction of unit balls, and Vaughan's remarks on Conway's construction, there is a paper by Denis Higgs (Proc. Koninklijke Nederlandse Akademie, Series A, Vol. 81, (4), 1978, pp.448-455) called: "A Universal Characterization of [0,\infty]", in which he gives such a characterization, based on a class of infinitary algebras in which the infinitary operation arises from the observation that every element of [0,\infty] can be wrtten as a sum, in general infinite, of fractions 1/{2^n} 's. Indeed, as Higgs' shows, this characterizes [0,\infty] as a free algebra of the appropriate kind on one generator. Cheers, Phil Scott From rrosebru@mta.ca Sun Jan 2 11:19:50 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA10222 for categories-list; Sun, 2 Jan 2000 10:16:16 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001012317.PAA16954@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: A couple of Y2K glitches In-reply-to: Your message of "Sat, 01 Jan 0100 11:37:15 GMT." Date: Sat, 01 Jan 2000 15:17:17 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: For a short while in the wee small hours of this morning, the US Naval Observatory was reporting the year as 19100. This is exactly 19 millennia after Peter Johnstone's distinctly post-Boadicean message on continued fractions, whose dateline reads Date: Sat, 1 Jan 100 11:37:15 +0000 (GMT) Granted the point of Y2K compliance was to avoid rolling back to the year 1900 by carrying a 1 into the hundreds position, but in hindsight that can be taken in various ways. Vaughan From rrosebru@mta.ca Sun Jan 2 16:37:32 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA14044 for categories-list; Sun, 2 Jan 2000 15:40:17 -0400 (AST) X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs Date: Sun, 2 Jan 2000 14:12:30 -0500 (EST) From: Michael Barr X-Sender: barr@triples.math.mcgill.ca To: categories@mta.ca Subject: categories: Re: Real interval halving In-Reply-To: <200001012203.OAA16605@coraki.Stanford.EDU> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Perhaps Vaughan is unfamiliar with the following definition of the reals. I got it from Steve Schanuel. I believe that he got it from Serge Lang and he probably got it from Emil Artin. Anyway, Let S be the ring of functions s: N --> N such that the function of two variables (m,n) |--> s(m+n) - s(m) - s(n) is bounded. Addition is element-wise and multiplication is functional composition. Let I consist of the bounded sequences. Then R = S/I. Interestingly, S is not commutative. We now have a real tangent line. Michael From rrosebru@mta.ca Mon Jan 3 17:24:00 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA32429 for categories-list; Mon, 3 Jan 2000 16:18:19 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 3 Jan 2000 10:28:18 -0500 (EST) From: Peter Freyd Message-Id: <200001031528.KAA12024@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Derivatives Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Given a center-preserving function between intervals, f, is there a natural way to obtain from it one that's midpoint-preserving? Part of preserving midpoints is preserving halving: f(hx) = hf(x). We can rewrite that to convert from a commutativity condition to a fixed- point condition: f = \x.2f(hx) (the fixed-pont of an operation that seems to be innate to every graphing calculator). The process needn't converge, indeed, one will often need to shrink the domain of the function down to a smaller concentric interval and it can converge to fixed-points not to our liking (such as \x.x*sin(2pi*log|x|/log2).) But the closed interval is the final coalgebra not just for the ordered-wedge functor X v X but for for the ordered-wedge of any positive number of copies of X. (There's a general theorem that says that a final coalgebra for X v X is automatically a final coalgebra for X v X v X v X, indeed, for any such ordered-wedge where the number of copies of X is a power of two. I haven't been able to find the proof for a general theorem that specializes to X v X v X.) Using that the closed interval is the final coalgebra for X v X v X we can define the thirding map t:I --> I in a manner similar to (and simpler than) the definition of the halving map. (Yes, the OED lists "third" as a verb) So we are also looking for solutions to f = \x.3f(tx). We obtain a commutative monoid of operators of the form \fx.nf(x/n). The process of applying a one-generator free monoid of operators easily generalizes to an arbitrary commutative monoid of operators. Starting with a center-preserving f between intervals the process needn't converge even if we restrict the domain to a smaller concentric interval. But if it does converge to the germ of a monotonic duality-preserving function then it converges to a germ of a midpoint-preserving function from the original source interval to the original target interval. And if these intervals should coincide, it converges to what in my last posting I defined as an element of the reals. From rrosebru@mta.ca Tue Jan 4 13:56:31 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id MAA16155 for categories-list; Tue, 4 Jan 2000 12:10:31 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Mime-Version: 1.0 X-Sender: street@hera.mpce.mq.edu.au Message-Id: In-Reply-To: References: Date: Tue, 4 Jan 2000 11:35:23 +1100 To: categories@mta.ca From: Ross Street Subject: categories: Re: Schanuel's reals Content-Type: text/plain; charset="us-ascii" ; format="flowed" Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Mike Barr writes: >Perhaps Vaughan is unfamiliar with the following definition of the reals. >I got it from Steve Schanuel. I believe that he got it from Serge Lang >and he probably got it from Emil Artin. I believe the idea *came* from Artin but I don't believe Artin was thinking of it as a *construction* of the reals. I was so taken by the construction that I thought it should be better known by tertiary teachers. I wrote a little note An efficient construction of the real numbers, Gazette Australian Math. Soc. 12 (1985) 57-58 on the construction (giving credit to Schanuel and reporting that Peter Johnstone told me Richard Lewis from Sussex had also come up with it). [Warning and Challenge: Steve pointed out that my note messes up the construction of the sup operation.] Happy 2000 plus. Ross From rrosebru@mta.ca Tue Jan 4 21:02:25 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA13581 for categories-list; Tue, 4 Jan 2000 19:50:43 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 4 Jan 2000 17:09:53 -0500 (EST) From: Peter Freyd Message-Id: <200001042209.RAA07909@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Sir Tony Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The Queen's New Years Honours list announced a knighthood for C.A.R. Hoare (the first person to find an application for 2-categories). From rrosebru@mta.ca Tue Jan 4 21:02:27 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA10170 for categories-list; Tue, 4 Jan 2000 19:51:15 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001041944.LAA09856@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Real interval halving In-reply-to: Your message of "Sun, 02 Jan 2000 14:12:30 EST." Date: Tue, 04 Jan 2000 11:44:07 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: It's true I only learned about the Artin(?)-Schanuel construction recently---Peter Freyd mentioned it to Phil Scott and me at lunch one day at LL'96 in Tokyo, albeit with yet another attribution, Conway. I thought it was very cute. There is some sort of duality that I don't understand between this construction and the Knuth-Pratt construction. The former puts the bounded sequences in the denominator and does the work in the numerator, namely requiring that s(m+n) = s(m) + s(n) to within a constant independent of m and n. The latter puts the bounded sequences in the numerator and does the work in the denominator, namely modding out by the equation x/2 + x/2 = x, where x/2 is defined as right shift (prepend zero). Artin-Schanuel can be related to Dedekind as follows. For Dedekind, the unreduced rationals m/n together with all m/0 constitute Z^2, the lattice points of the plane, whose nonempty rays are then the reduced rationals. The irrationals along with infinity (thinking of the real line projectively) are then obtained as the empty rays, all of which make distinct Dedekind cuts in the rationals, qua rays *or* qua irreduced rationals (actually two cuts are needed in the projective line, infinity supplies the other). Artin-Schanuel identifies all but the ray at infinity in terms of their neighborhoods instead of cuts, specifying one point of the neighborhood per column. Moving the bounded sequences from the denominator to the numerator doesn't seem to be compatible with this picture. What picture if any is it compatible with? And is there a categorical duality that goes along with this inversion? A passage from algebra to coalgebra perhaps? Or is it the duality of addition and multiplication---we have s(m+n) = s(m) + s(n) doing the work above and x/2 + x/2 = x at work underneath, albeit with addition also party to the latter. Vaughan From rrosebru@mta.ca Tue Jan 4 21:04:03 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA03870 for categories-list; Tue, 4 Jan 2000 19:51:44 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001042018.MAA10019@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Real interval halving In-reply-to: Your message of "Sun, 02 Jan 2000 14:12:30 EST." Date: Tue, 04 Jan 2000 12:18:33 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: (That bit about + being in x/2 + x/2 = x was silly, 2(x/2) = x is of course fine. -Vaughan) From rrosebru@mta.ca Tue Jan 4 21:08:49 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA10909 for categories-list; Tue, 4 Jan 2000 19:52:55 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 4 Jan 2000 12:24:54 +1100 (EST) Message-Id: <200001040124.MAA12473@algae.socs.uts.EDU.AU> To: categories@mta.ca Subject: categories: two research positions From: Barry Jay Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: ** apologies for multiple postings ** University of Technology, Sydney School of Computing Sciences ________________________________________________________ Two Research Positions ________________________________________________________ We have recently been awarded a 3-year grant from the Australian Research Council for our project Shape-based programming: sharpening the tools This project will develop a new programming language, FISh2 which combines the expressive power of functorial polymorphism as developed in Functorial ML with the efficient execution based on shape analysis, as developed in FISh1. FISh2 will support both functional and imperative programming styles across a wide range of data types. A key application area is high-performance computing, where high expressivity and performance are both key issues. A second goal is to develop a specialised version of FISh, called GoldFISh, which supports a shape-based cost model that is able to predict performance across a wide range of parallel architectures. Postdoctoral Research Fellow ---------------------------- The postdoctoral research fellow will take a key role in the implementation of FISh2. This will require broad understanding of typed programming languages, the ability to convert high-level language designs, often expressed in formal logical notation, into implementations written in both functional and imperative styles. They must be willing to learn the principles of shape theory. A doctorate in a relevant branch of computer science or mathematics is essential, as is the demonstrated ability in at least one of the areas of compiler construction, semantics of programming languages or parallel programming. Knowledge of some of type theory, term rewriting, functional programming, skeletons or data distribution strategies is desirable. The applicant must have personal skills adequate to work in a small team with both senior and junior colleagues, and written communication skills appropriate for producing clearly documented code, user documentation, material suitable for the web-site, and formal papers for refereed publication. The position is full-time for three years at a salary of Australian $43,254 - $55,418 p.a. beginning early in 2000. Research Assistant Grade 2 -------------------------- The second assistant will develop most of the benchmarking programs necessary to establish that FISh2 and GoldFISh have the properties we claim for them. This will require the ability to learn novel, and unstable programming languages without adequate documentation. They must be able to give informal feedback on the usability of the language. They must understand the basic principles of parallel programming. They must use these languages to encode applications from science and engineering, and perform tests to capture execution properties. They must be willing to assist in other duties, such as web-site maintenance, as required. They will be set weekly goals, and expected to seek help actively when necessary. A first degree in a relevant branch of computer science is essential, as is some knowledge of functional programming, the use of types in programming, and principles of program testing and benchmarking. Experience in system development is desirable. Both Positions --------------- Address initial enquiries to Associate Professor Barry Jay, Phone: (612) 9514 1814 E-mail: cbj@socs.uts.edu.au Applications should address the selection criteria available from the School of Computing Sciences web site on http://www.socs.uts.edu.au/posvacant/ or from Recruitment on (612) 9514 1087 and list name, address, phone and fax numbers and email addresses of three referees, and quote the appropriate Reference Number above. Applications should be forwarded by 15th February, 2000 to: THE RECRUITMENT OFFICER, UNIVERSITY OF TECHNOLOGY, SYDNEY PO BOX 123, BROADWAY, NSW 2007 Interviews will be conducted in early March, 2000. Equal Employment Opportunity is University policy. UNIVERSITY OF TECHNOLOGY, SYDNEY POSITION DESCRIPTION Research Assistant, Grade 7-8 Incumbent: Date: 18/11/99 Reports to: C.B. Jay Written by: C.B. Jay Faculty: Maths and Computing Sciences School: Computing Sciences Location: City, Building 4, 5th floor Approvals: Position: 1: J Edwards: _____________ Head of School, Computing Sciences 2: G McLelland: _______________ Acting Dean, Faculty of Maths & Computing Sc 3: ____________________ ____________________________ ________________________________________________________ ACCOUNTABILITY OBJECTIVE The research assistant is responsible for supporting A/Prof C.B. Jay and Dr G. Keller in achieving the goals of their ARC large grant (2000-2002) "Shape-based programming: sharpening the tools". DIMENSIONS $ value of grant: $56,000 - 60,000 p.a. Period of grant: 3 years No. of staff: 1 NATURE AND SCOPE The University's mission is to produce the highest quality education for the professions at both undergraduate and postgraduate level and to carry out research and consultancy of relevance to industry and business. The University is spread over four campuses in the Sydney metropolitan area. Approximately 22,000 students are enrolled in the University's ten faculties, which offer a broad spectrum of undergraduate, postgraduate and continuing professional education programs. The administrative and academic support functions of the University are undertaken by five divisions. The University employs approximately 1100 support staff and 1150 academic permanent and fixed term staff, plus approximately 800 casual academic staff. The University also has interest in two companies - Insearch Limited and the Sydney Education Broadcasting Limited and has several associated research and technology centres. The School of Computing Sciences sits within the Faculty of Maths and Computing Sciences. It has a well established research history and is very active in a range of research areas with a number of research support staff and doctoral students. This research position would support activities in the Information Systems section of the School. This area researches and teaches the informational, human and organisational aspects of computing. The area is well situated in terms of its interest and expertise in the areas of the management of information systems change and the use of qualitative research methods in information systems research. ACCOUNTABILITY RELATIONSHIP The research assistant will report to A/Prof C.B. Jay. MAJOR TASKS: - A major role in constructing compilers for the programming languages FISh2 and GoldFISh, their testing and optimisation. - documentation of their work in a form suitable for external distribution - support for the FISh web-site - participate in project meetings and actively engage with other project members. CONSTRAINTS The incumbent in consultation with the Principal Researcher determines research strategies and priorities. CHALLENGES The incumbent must be able to produce high quality implementations of designs which incorporate cutting edge ideas that are not completely fixed. RELATIONSHIPS The Research Assistant Level 7-8 will liaise on most days with other research team members to ensure the progress of the research, to discuss results obtained, improvements to techniques and future work. The incumbent will be expected to liaise with external users of our prototypes. PRINCIPAL ACCOUNTABILITIES Produces working implementations as required. Contributes to the production of publishable research papers. UNIVERSITY OF TECHNOLOGY, SYDNEY POSITION DESCRIPTION Research Assistant, Grade 2 Incumbent: Date: 18/11/99 Reports to: C.B. Jay Written by: C.B. Jay Faculty: Maths and Computing Sciences School: Computing Sciences Location: City, Building 4, 5th floor Approvals: Position: 1: J Edwards: _____________ Head of School, Computing Sciences 2: G McLelland: _______________ Acting Dean, Faculty of Maths & Computing Sc 3: ____________________ ____________________________ ________________________________________________________ ACCOUNTABILITY OBJECTIVE The research assistant is responsible for supporting A/Prof C.B. Jay and Dr G. Keller in achieving the goals of their ARC large grant (2000-2002) "Shape-based programming: sharpening the tools". DIMENSIONS $ value of grant: $57,000 Period of grant: 1 years No. of staff: 1 NATURE AND SCOPE ACCOUNTABILITY RELATIONSHIP The research assistant will report to A/Prof C.B. Jay. MAJOR TASKS: - Development and execution of benchmark programs for our new programming languages FISh2 and GoldFISh. - documentation of their work in a form suitable for external distribution - support for the FISh web-site - participate in project meetings and actively engage with other project members. CONSTRAINTS The incumbent in consultation with the Principal Researcher determines research strategies and priorities. CHALLENGES The incumbent must be able to master novel programming techniques which have never been used in large programs before. RELATIONSHIPS The Research Assistant Level 5-6 will liaise on most days with other research team members to ensure the progress of the research, to discuss results obtained, improvements to techniques and future work. The incumbent will be expected to liaise with external users of our prototypes. PRINCIPAL ACCOUNTABILITIES Produces working programs, and test results as required. Contributes to the production of publishable research papers. Maintains the FISh web-site. From rrosebru@mta.ca Wed Jan 5 12:04:33 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA24183 for categories-list; Wed, 5 Jan 2000 10:24:15 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: Subject: categories: CL2000: 3rd call for papers To: categories@mta.ca Date: Wed, 5 Jan 2000 13:55:33 +0100 (MET) From: "Raamsdonk van F" X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: *** apologies for multiple copies *** First International Conference on Computational Logic, CL2000 Imperial College, London, UK 24th to 28th July, 2000 http://www.doc.ic.ac.uk/cl2000 3rd call for papers The deadline for submission of papers to CL2000 is FEBRUARY 1, 2000. Papers on all aspects of the theory, implementation, and application of Computational Logic are invited, where Computational Logic is to be understood broadly as the use of logic in Computer Science. Papers can be submitted to one the following seven streams of CL2000 (each stream has its own separate program committee): - Database Systems (DOOD2000) - Program Development (LOPSTR2000) - Knowledge Representation and Non-monotonic Reasoning - Automated Deduction: Putting Theory into Practice - Constraints - Logic Programming: Theory and Extensions - Logic Programming: Implementations and Applications The last three streams effectively constitute the former ICLP conference series that will be now integrated into CL2000. Please note the following: - Further details on formatting of the papers, publisher, etcetera are available via the webpage of the conference. - Authors will be notified of acceptance/rejection by 15th April, 2000. - Camera-ready versions must be received by 15th May, 2000. CL2000 is co-locating with ILP2000, the 10th International Conference on Inductive Logic Programming. The call for papers of ILP2000 (deadline for submission of papers: 29 March 2000) and further information is available via http://www.cs.york.ac.uk/ILP-events/ILP-2000 From rrosebru@mta.ca Wed Jan 5 12:04:20 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA25660 for categories-list; Wed, 5 Jan 2000 10:23:52 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: To: categories@mta.ca Subject: categories: Announcement: EXTENDED DEADLINE FOR CMCS'2000 Date: Wed, 05 Jan 2000 13:21:41 +0100 From: Jan Rutten Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: EXTENDED DEADLINE FOR CMCS'2000: Due to the Y2K bug scare the deadline for submissions to CMCS'2000 is extended to 17 January 2000!!!!! The other dates of the following CFP do not change: **************************************************************************** ****** C A L L F O R P A P E R S for the WORKSHOP ON COALGEBRAIC METHODS IN COMPUTER SCIENCE (CMCS'2000) Scope State-based dynamical systems as found throughout computing science are traditionally described as transition systems or certain kinds ofautomata. During the last decade, it has become increasingly clear that such systems can be captured uniformly as so-called ``coalgebras'' (which are the formal dual of algebras). Coalgebra is beginning to develop into a field of its own, with its own proof-methods (involving bisimulations and invariants). This workshop will be devoted to both an introduction to basic coalgebraic notions and techniques, and also to some recent advances in the theory of coalgebras. We are looking for participants and contributed talks to this informal workshop on both the theory and the use of coalgebras in computer science. The workshop will consist of two days, preceding the ETAPS conference (25-26 March, 2000) at the Technical University of Berlin. More information regarding submissions is given below. The scope of the meeting includes the following themes: - the theory of coalgebras (including set theoretic and categorical approaches); - coalgebras as computational and semantical models (for programming languages, dynamic systems, etc.); - coalgebras in (functional, object-oriented, concurrent) programming; - coalgebras and data types; - (coinductive) definition and proof principles for coalgebras (with bisimulations or invariants); - coalgebras and (hidden-sorted) algebras; - coalgebraic specification and verification; - coalgebras and (modal) logic Organization: Bart Jacobs (Nijmegen), Horst Reichel(Dresden), Jan Rutten (CWI, Amsterdam) and Larry Moss (Bloomington, IN). Program Committee: H. Peter Gumm (Marburg), Bart Jacobs (Nijmegen), Ugo Montanari (Pisa), Larry Moss (Bloomington, IN), Ataru T. Nakagawa (Tokyo), John Power (Edinburgh), Horst Reichel (Dresden), Jan Rutten (CWI, Amsterdam). Submissions The following dates are important for submission to the ENTCS volume. - 3 January 2000: deadline for submissions. - 11 February 2000: notification of acceptance. - 3 March 2000: final version. - 25-26 March 2000: workshop, where a printed version of the ENTCS issue will be available for participants. - (25 March - 2 April, 2000: ETAPS conference). The ideal submission is not longer than 20 pages, and gives a clear exposition of the relevant ideas. It can be sent by email to: Horst Reichel, or by ordinary mail to: Horst Reichel TU Dresden, Faculty of Computer Science Institute: Theoretical Computer Science D-01062 Dresden Germany The informations will be actualized on the following web page: http://wwwtcs.inf.tu-dresden.de/~reichel/cmcs.html From rrosebru@mta.ca Fri Jan 7 16:23:52 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id OAA01982 for categories-list; Fri, 7 Jan 2000 14:03:31 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 07 Jan 2000 15:57:24 +0100 From: POWELL Olivier Subject: categories: Reminder: ICALP call for paper To: Powell Olivier Message-id: <3875FED4.D70CC46D@cui.unige.ch> Organization: =?iso-8859-1?Q?Universit=E9?= de =?iso-8859-1?Q?Gen=E8ve?=, =?iso-8859-1?Q?d=E9partement?= informatique MIME-version: 1.0 X-Mailer: Mozilla 4.7 [en] (X11; I; SunOS 5.6 sun4u) Content-type: MULTIPART/MIXED; BOUNDARY="Boundary_(ID_Z0nUk4ToRFq4wHuJZ8SyGw)" X-Accept-Language: en Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: This is a multi-part message in MIME format. --Boundary_(ID_Z0nUk4ToRFq4wHuJZ8SyGw) Content-type: text/plain; charset=us-ascii Content-transfer-encoding: 7bit --Boundary_(ID_Z0nUk4ToRFq4wHuJZ8SyGw) Content-type: text/plain; name=cfp; charset=us-ascii Content-disposition: inline; filename=cfp Content-transfer-encoding: 7bit Call for Papers ICALP'2000 27-th International Colloquium on Automata, Languages and Programming July 9-15, 2000, Geneva, Switzerland The 27-th annual meeting of the European Association of Theoretical Computer Science will be held in Geneva, Switzerland. As is the case of the two tracks of the journal Theoretical Computer Science, the scientific program of the Colloquium is split into two parts: Track A of the meeting will correspond to Algorithms, Automata, Complexity, and Games, while Track B will correspond to Logic, Semantics and Theory of Programming. Original contributions to theory of computer science, to be presented either in Track A or in Track B, are being sought. Authors are invited to submit extended abstracts of their papers, not exceeding 12 pages in the standard Springer Verlag LNCS style. Instructions for paper submissions can be found at the conference web page. Authors from countries where access to Internet is difficult may mail a single copy of their paper directly to the address of the conference chairman. Submissions should consist of: a cover page, with the author's full name, address, fax number, e-mail address, a 100-word abstract, keywords, and to which track (A or B) the paper is being submitted and an extended abstract describing original research in no more than 12 pages. It is expected that accepted papers will be presented at the conference. Simultaneous submission to other conferences with published proceedings is not allowed. Conference Chair: Jose D. P. Rolim Centre Universitaire d'Informatique University of Geneva 24 rue du General Dufour 1211 Geneva 4 Switzerland mailto:icalp@cui.unige.ch ICALP'2000 Program Committee Track A: Emo Welzl, Chair, ETH Zuerich Harry Buhrman, CWI Amsterdam Peter Bro Miltersen, Univ. Aarhus Martin Dietzfelbinger, Techn Univ Ilmenau Afonso Ferreira, CNRS-I3S-INRIA Sophia Antipolis Marcos Kiwi, Univ. de Chile Jens Lagergren, KTH Stockholm Gheorghe Paun, Romanian Acad. Guenter Rote, Techn. Univ. Graz Ronitt Rubinfeld, Cornell Univ. Amin Shokrollahi, Bell Labs Luca Trevisan, Columbia Univ. Serge Vaudenay, ENS Paris Uri Zwick, Tel Aviv Univ. Track B: Ugo Montanari, Chair, Univ. of Pisa Rajeev Alur, Univ. Pennsylvania, Philadelphia Rance Cleaveland, SUNY at Stony Brook Pierpaolo Degano, Univ. of Pisa Jose Fiadeiro, Univ. of Lisbon Andy Gordon, Microsoft Research, Cambridge, Orna Grumberg, Technion, Haifa Claude Kirchner, Inria, Nancy Mogens Nielsen, Univ. of Aarhus Catuscia Palamidessi, Penn. State Univ, Univ. Park Joachim Parrow, KTH, Stockholm Edmund Robinson, QMW, London Jan Rutten, CWI, Amsterdam Jan Vitek, Univ. of Geneva Martin Wirsing, Ludwig-Maximilians-University, Munich Pierre Wolper, Univ. of Liege. Special Award Richard Karp, Berkeley Invited Speakers Track A: Andrei Broder, Altavista Oded Goldreich, MIT and Weizman Inst. Johan Haastad, KTH Stockholm Kurt Mehlhorn, Max Plank Institute Track B: Samsom Abramsky, Edinburgh U. Gregor Engels, Paderborn U. Roberto Gorrieri, U. Bologna Zohar Manna, Stanford U. Satellite Workshops * Workshop on Randomization and Approximation in CS. (RANDOM'2000) * Workshop on Algorithms for Communication Networks (ARACNE) * Workshop on Boolean Functions and Applications * Workshop on Intersection Types and Related Systems (ITRS '00) * Workshop on Graph Transformation and Visual Modeling Techniques * Workshop on Process Algebra and Performance Models (PAPM 2000) * Workshop on Theor. Found. of Security Analysis and Design (IFIP WG 1.7) General Information Geneva is situated along the banks of Lac Leman and Le Rhone. The lake showcases the plumed fountain Jet d'Eau, and various districts of Geneva are connected by bridges across the waterways. The University of Geneva where ICALP '00 will convene is located on the `Left Bank' off Place Neuve and along the Promenade des Bastions near the Old Town section of Geneva. Geneva is a city of water parks and gardens and welcoming walkways which encourage exploration of the historical sites, museums, and international business and shopping districts. The University of Geneva is located near `Old Town' an area dotted with sidewalk cafes, student life, and building antiquities dating back to the 5th century. Geneva is a crossroads situated in the heart of Europe and linked to the world by a vast network of motorways, airlines and railways. For those planning to attend ICALP '00 in Geneva, it is an excellent opportunity to organize short trips into the countryside of charming villages and vineyards. Tours to please all ages and interests are available including afternoon train excursions, shopping cruises on Lake Geneva and The Rhone, and bus and cablecar trips in the Alps. For some, the most inviting attraction will be mouintain climbing. Mont Blanc, one of the highest points in Europe and the city of Chamonix are less than an hour away. Accomodations at a very special ICALP rate have been reserved in a couple of hotels and very inexpensive rooms will be available at the Student Housing. Lunch will be served daily on campus and there will be morning and afternoon refreshment breaks. Note that the specially priced hotel accommodations reserved for ICALP participants are located only a 5-10 minute walk to the campus. Important Dates Workshop Proposals: November 10,1999 Submissions: January 17, 2000 Notification: March 21, 2000 Final Copies: April 18, 2000 Further Information Further information related to ICALP'00, with instructions for paper submissions and conference registration, as well as with details on conference site, registration fee, accommodation, social program, and payments, will appear at the conference webpage at http://cuiwww.unige.ch/~icalp and in forthcoming issues of EATCS Bulletin. The conference is organized by the Centre Universitaire d'Informatique of the University of Geneva. --Boundary_(ID_Z0nUk4ToRFq4wHuJZ8SyGw)-- From rrosebru@mta.ca Sat Jan 8 12:52:42 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA31986 for categories-list; Sat, 8 Jan 2000 11:58:34 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <20000108012944.34897.qmail@hotmail.com> X-Originating-IP: [194.18.4.243] From: "Lars Lindqvist" To: categories@mta.ca Subject: categories: Diagrams on the WWW ? Date: Sat, 08 Jan 2000 02:29:44 CET Mime-Version: 1.0 Content-Type: text/plain; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Hi, My name is Lars Lindqvist and I wonder if there are any packages which makes it possible to include diagrams in documents on the WWW in a conveniant manner? What I have in mind are packages similar to the existing packages for the creation of diagrams in e.g. LaTex. Very simple diagrams can probably be specified using the table construct in MathML but problems occur quite rapidly as the diagrams become more complicated. MathML is simply not intended for specification of such diagrams. See e.g. the last paragraph in section 7.1.5.2 of the MathML specification http://www.w3.org/TR/1999/WD-MathML2-19991222: " Finally, apart from the introduction of new glyphs, many of the situations where one might be inclined to use an image amount to some sort of labeled diagram. For example, knot diagrams, Venn diagrams, Dynkin diagrams, Feynman diagrams and complicated commutative diagrams all fall into this category. As such, their content would be better encoded via some combination of structured graphics and MathML markup. Because of the generality of the `labeled diagram' construction, the definition of a markup language to encode such constructions extends beyond the scope of the W3C Math activity. (See http://www.w3.org/Graphics for further W3C activity in this area.) " Following this suggestion I have made some initial attemts to construct an XML markup language for diagrams. I have also written a XSL (Extensible Stylesheet Language) schema that transforms diagrams specified in this language to a VML (Vector Markup Language) specification which can be rendered by e.g. Internet Explorer 5. There is a lot of work involved in a project like this so I am really interested to hear about other attempts and experiences before I continue. /Lars Lindqvist ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com From rrosebru@mta.ca Sun Jan 9 13:45:30 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id MAA04910 for categories-list; Sun, 9 Jan 2000 12:33:06 -0400 (AST) X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs Date: Sat, 8 Jan 2000 17:38:52 -0500 (EST) From: Michael Barr X-Sender: barr@triples.math.mcgill.ca To: categories@mta.ca Subject: categories: Re: Diagrams on the WWW ? In-Reply-To: <20000108012944.34897.qmail@hotmail.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: I would suggest doing it in tex and then converting it to pdf, which is quickly coming to be a standard for the web. There are at least two ways of doing tex --> pdf that cost no money. (You can also get Adobe distiller, but that costs actual money.) There is something called pdflatex, that I have not used but it comes free with the tex distribution from CTAN (it is essentially undocumented, so if you figure it out, I would like to know about how it works. A second, not entirely satisfactory is to use the ability of gsview to output pdf files. You choose print to disk and then you get a pdf file that can be read with the Adobe reader. It is common practice to put a link to the free download of the Adobe reader when you post a pdf file, but most users of the web probably have it by now. Michael Barr From rrosebru@mta.ca Sun Jan 9 13:43:46 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id MAA08770 for categories-list; Sun, 9 Jan 2000 12:37:51 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: pt@dcs.qmw.ac.uk Date: Sun, 9 Jan 2000 13:01:47 GMT Message-Id: <200001091301.NAA17819@koi-pc.dcs.qmw.ac.uk> To: categories@mta.ca Subject: categories: diagrams on the web Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Dear Lars, A propos of your message to categories, I really cannot understand why anyone would want to use any (existing) language other than LaTeX for writing mathematics. HTML and its developments seem to me to be much less expressive and much more bureaucratic, especially for writing (ordinary) mathematics. That readers using the web have inferior browsers is, to me, an argument for developing and promoting better browsers, not for forcing mathematical authors to use worse mark-up languages. With existing web technology, there are ways of putting LaTeX formulae, diagrams, etc on web pages by translating them into PostScript and then GIF files (LaTeX2HTML does this). For simple mathematical formulae, TTH makes full use of the (limited) features of HTML, without using GIFs, and is what I used to translate my book into HTML (though I had to write a substantial program to simplify by LaTeX before TTH could cope with it). Regarding diagrams, my view is that there is no "generic" diagram problem - particular kinds of diagram are for me two-dimensional variations on particular kinds of formal languages. My own TeX package does a good job of commutative diagrams for certain (but not all) parts of category theory. It is conceived as a way in which to write two-dimensional formulae, not as a way of "drawing". Paul http://www.dcs.qmw.ac.uk/~pt/diagrams http://www.dcs.qmw.ac.uk/~pt/book ("Practical Foundations of Maths") From rrosebru@mta.ca Mon Jan 10 11:07:28 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA10681 for categories-list; Mon, 10 Jan 2000 09:35:50 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Robert Tennent Date: Sun, 9 Jan 2000 14:07:30 -0500 (EST) Message-Id: <200001091907.OAA18995@maggie.cs.queensu.ca> To: barr@barrs.org, categories@mta.ca Subject: categories: Re: Diagrams on the WWW ? Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > From: Michael Barr > > I would suggest doing it in tex and then converting it to pdf, which is > quickly coming to be a standard for the web. There are at least two ways > of doing tex --> pdf that cost no money. There is something called > pdflatex. Still beta I believe, but works well. > A second, not entirely > satisfactory is to use the ability of gsview to output pdf files. You > choose print to disk and then you get a pdf file that can be read with the > Adobe reader. > Best results are obtained by using type 1 fonts and the most recent version of ghostscript, currently 5.97, or maybe 6. Another possibility, which I've found gives the best results, is to use a free program called dvipdfm: http://odo.kettering.edu/dvipdfm/ Bob T. From rrosebru@mta.ca Mon Jan 10 11:10:54 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA16757 for categories-list; Mon, 10 Jan 2000 09:40:29 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 10 Jan 2000 14:57:41 +1100 (EST) Message-Id: <200001100357.OAA15318@algae.socs.uts.EDU.AU> To: categories@mta.ca Subject: categories: functorial lambda calculus From: Barry Jay Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: The following report is available from: Comments most welcome. Barry Jay ------------------------------------------------------------------- Functorial Lambda-calculus C. Barry Jay Functorial lambda-calculus represents some type constructors as functors, whose quantification supports new forms of polymorphism. This is exploited by a powerful new generic programming technique, called program extension, whose evaluation does not use explicit types. It can be used to define all the standard second-order combinators, for mapping, folding, etc. so that they apply to arbitrary data types. It can also be used to define generic functions for equality, addition, assignment and shape. In particular, shape evaluation can be used to support static specialisation, and to reduce space usage. This paper introduces the calculus, provides a type inference algorithm, and shows how to augment its expressive power and improve its efficiency by adding more constructions and optimising evaluation. From rrosebru@mta.ca Mon Jan 10 11:19:19 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA21139 for categories-list; Mon, 10 Jan 2000 09:36:28 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <20000109193941.99363.qmail@hotmail.com> X-Originating-IP: [194.18.4.243] From: "Lars Lindqvist" To: categories@mta.ca Subject: categories: Re: Diagrams on the WWW ? Date: Sun, 09 Jan 2000 20:39:41 CET Mime-Version: 1.0 Content-Type: text/plain; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Paul and Michael, There is perhaps no realistic alternative to LaTeX for writing mathematics today, but MathML is a language for the future and I like the visions and the goals associated with this language. I will not try to argue for MathML here because this is done in the specification (actually a draft) at http://www.w3.org/TR/1999/WD-MathML2-19991222. As discussed in Section 1.3.1 (Layered Design of Mathematical Web Services) MathML provides the lower level of a two layer architecture where LaTeX would be a language (tool) at the higher level (generating MathML code). There already exists several different tools for converting LaTeX to MathML so a straightforward solution would be to construct a converter also for some popular diagram specification language (package). Since MathML does not support the specification of complicated labelled diagrams the output would be a mixture of MathML and e.g. VML (or SVG) which are markup languages for vector graphics. This would also be in accordance with Section 7.1.5.2 of the MathML specification. So I suppose I have to reformulate my question from my first letter and ask whether there are any such tools or converters? I do not know much about the PDF format. When I publish a document written in LaTeX on the web I usually generate a postscript version and a PDF version (generated using Adobe distiller). Thanks for your replies. Lars L ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com From rrosebru@mta.ca Mon Jan 10 11:20:55 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA18559 for categories-list; Mon, 10 Jan 2000 09:38:23 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: From: Robert Harper To: categories@mta.ca Subject: categories: RE: Diagrams on the WWW ? Date: Sun, 9 Jan 2000 19:44:18 -0500 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2650.21) Content-Type: text/plain; charset="iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: MikTeX, a free TeX implementation for PC's (and possibly other platforms, I'm not certain) comes with a dvi-to-pdf converter, called dvipdfm. Use it just like dvips, and you get pdf format. Bob Harper From rrosebru@mta.ca Mon Jan 10 12:41:37 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA17104 for categories-list; Mon, 10 Jan 2000 11:14:51 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 10 Jan 2000 10:35:24 +0100 From: POWELL Olivier Subject: categories: ICALP: dead line extended to january 24th. To: categories@mta.ca Message-id: <3879A7DB.A9856C4A@cui.unige.ch> Organization: =?iso-8859-1?Q?Universit=E9?= de =?iso-8859-1?Q?Gen=E8ve?=, =?iso-8859-1?Q?d=E9partement?= informatique MIME-version: 1.0 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: [from moderator: see earlier message for full CFP which is not being retransmitted] EXTENSION OF DEADLINE FOR PAPER SUBMISSION TO JANUARY 24TH, 2000 . From rrosebru@mta.ca Mon Jan 10 17:55:11 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA09508 for categories-list; Mon, 10 Jan 2000 16:32:33 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <387A3B84.C03598E6@sun.iwu.edu> Date: Mon, 10 Jan 2000 14:05:24 -0600 From: Larry Stout X-Mailer: Mozilla 4.51 [en] (X11; I; Linux 2.2.5-15 i686) X-Accept-Language: en MIME-Version: 1.0 To: Categories List Subject: categories: Call for Papers: Linz2000 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: -------------------------------------------------------------------------------- Call for Papers: Linz2000 Mathematical Aspects of Non-Classical Logics and Fuzzy Inference To be held at Bildungszentrum St. Magdalena, Linz, Austria June 13-18, 2000 Sponsored by: FLLL Fuzzy Logic Laboratorium Linz - Hagenberg ------SHORT DESCRIPTION OF SEMINAR PURPOSE/MISSION------- Since their inception in 1979 the Linz Seminars on Fuzzy Sets have emphasized the development of mathematical aspects of fuzzy sets by bringing together researchers in fuzzy sets and established mathematicians whose work outside the fuzzy setting can provide direction for further research. The seminar is deliberately kept small and initimate so that informal critical discussion remains central. There are no parallel sessions and during the week there are several round tables to discuss open problems and promising directions for further work. Linz2000 will be the 21st seminar carrying on this tradition. Linz2000 will deal with Mathematical Aspects of Non-classical Logics and Fuzzy Inference. It is the hope of the organizers that the talks will provide a mathematical setting for both the theory and the practice of logical means of dealing with inference under uncertainty, limited resources, modalities of place, time, and state of knowledge. This Seminar will consider, but not be limited to, the following topics in logic: 1. Categorical Logic 2. Logic of cognition 3. Fuzzy Inference 4. Modal Logics 5. Many Valued Logics 6. Logics taking into account time, place, vagueness, and limited resources The total number of participants is usually bounded above by 40 with broad international representation and a mix of pure and applied interests. Invited talks are usually allowed an hour and a half and contributed talks 45 minutes. There are no parallel sessions. The Seminar will feature ample time for discussion of each presentation, a fundamental aspect of the Linz tradition. The schedule allows for daily round tables for discussion of open problems and issues raised by the day's talks. If you are interested in giving a contributed talk, please submit an abstract of no more than 650 words to the Program Chair, Lawrence Stout. The deadline for all submissions is 15 February 2000; and you should be notified no later than 15 April, 2000 concerning acceptance of your presentation into the Seminar. It is preferred that your submission be made by e-mail, in which case it is also preferred that this submission be a LaTeX 2e (or 2.09) file in ASCII: please, no zipped files. The subject line for such an e-mail should include the phrase Linz2000 Seminar and it should be addressed to lstout@sun.iwu.edu It would also be helpful if your submission included your snail-mail address, fax number, and any additional e-mail addresses or phone numbers that you deem helpful. PROGRAM COMMITTEE Lawrence N. Stout, Bloomington (IL, USA) - Chairman Dan Butnariu, Haifa (Israel) Didier Dubois, Toulouse (France) Lluis Godo, Barcelona (Spain) Siegfried Gottwald, Leipzig (Germany) Ulrich Ho"hle, Wuppertal (Germany) Erich Peter Klement, Linz (Austria) Wesley Kotze';, Grahamstown (South Africa) Radko Mesiar, Bratislava (Slovakia) Daniele Mundici, Milano (Italy) Endre Pap, Novi Sad (Yugoslavia) Stephen E. Rodabaugh, Youngstown (OH, USA) Marc Roubens, Liège (Belgium) Aldo Ventre, Napoli (Italy) Siegfried Weber, Mainz (Germany) EXECUTIVE COMMITTEE Erich Peter Klement Ulrich Ho"hle Stephen E. Rodabaugh Siegfried Weber -- Lawrence Neff Stout Professor of Mathematics Illinois Wesleyan University http://www.iwu.edu/~lstout From rrosebru@mta.ca Tue Jan 11 10:08:31 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id IAA06290 for categories-list; Tue, 11 Jan 2000 08:49:00 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 11 Jan 2000 11:19:17 +1100 (EST) Message-Id: <200001110019.LAA15790@algae.socs.uts.EDU.AU> To: categories@mta.ca Subject: categories: URL for functorial lambda-calculus From: Barry Jay Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: My apologies to all those who tried to access the paper "Functorial lambda-calculus". The correct URL is http://www-staff.socs.uts.edu.au/~cbj/Publications/fl_report.ps.gz Thanks to all those who contacted me directly. Barry ************************************************************************* | Associate Professor C.Barry Jay, | | Reader in Computing Sciences Phone: (61 2) 9514 1814 | | Head, Algorithms and Languages Group, Fax: (61 2) 9514 1807 | | University of Technology, Sydney, e-mail: cbj@socs.uts.edu.au | | P.O. Box 123 Broadway, 2007, http://www-staff.socs.uts.edu.au/~cbj | | Australia. FISh homepage ... ~cbj/FISh | ************************************************************************* From rrosebru@mta.ca Wed Jan 12 11:48:21 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA16741 for categories-list; Wed, 12 Jan 2000 09:42:58 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Jiri Adamek Message-Id: <200001121243.NAA03979@lisa.iti.cs.tu-bs.de> Subject: categories: Reals and rationals To: categories@mta.ca Date: Wed, 12 Jan 100 13:43:47 +0100 (MET) X-Mailer: ELM [version 2.4ME+ PL28 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: This is a comment to the recently discussed Pavlovic-Pratt paper: M. Barr has proved in "Terminal Coalgebras ..."( TCS 114) that for bicontinuous set functors initial algebras carry a natural metric, and a Cauchy completion of that space is a final coalgebra. This result can be generalized to endofunctors F of any locally finitely presentable category. Side conditions: F preserve monomorphisms and have a point in F(O). Of the two functors used by Dusko and Vaughan, only F_2 satisfies the latter, of course. Its initial algebra is the set of all rationals in [O,1), which illustrates the idea quite well. The statement of the generalization I have in mind is that the structure of a final coalgebra T (which in a locally finitely presentable category is determined by morphisms from all finitely presentable objects B into T) is determined by the structure of an initial algebra I in the following sense: each hom(B,I) carries a natural metric and a Cauchy completion is hom(B,T). Thus, for endofunctors of Pos not only the elements of T but also its order is obtained by completing I . Jiri Adamek From rrosebru@mta.ca Wed Jan 12 11:55:24 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA17566 for categories-list; Wed, 12 Jan 2000 09:40:21 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Received: from zent.mta.ca (zent.mta.ca [138.73.101.4]) by mailserv.mta.ca (8.9.3/8.9.3) with SMTP id TAA30425 for ; Tue, 11 Jan 2000 19:53:32 -0400 (AST) X-Received: FROM hotmail.com BY zent.mta.ca ; Tue Jan 11 20:12:30 2000 X-Received: (qmail 36998 invoked by uid 0); 11 Jan 2000 23:53:24 -0000 Message-ID: <20000111235324.36997.qmail@hotmail.com> X-Received: from 200.36.184.161 by www.hotmail.com with HTTP; Tue, 11 Jan 2000 15:53:24 PST X-Originating-IP: [200.36.184.161] Mime-Version: 1.0 Content-Type: text/plain; format=flowed From: Steve Schanuel To: categories@mta.ca Subject: categories: Re: Tate reals Date: Tue, 11 Jan 2000 15:53:24 PST Mime-Version: 1.0 Content-Type: text/plain; format=flowed Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: My ´construction´of the reals, referred to by Ross and Mike, came fom an observation of Tate about bilinear maps many years earlier, which essentially goes back to Eudoxus. I take the task to be relating the continuous to the discrete, rather than constructing the former from the latter, but never mind. R is the ring of endomorphisms E(T(L))of the group T(L) of translations (rigid maps at finite distance from the identity) of the line L. If we start instead with a discrete line D (a line of dots), then T(D) is isomorphic to Z (additive group without preferred generator). E(T(D) is the ring Z, but instead take A(T(D)), ¨almost homomorphisms¨ Z to Z. A(T(D)) is an additive group with a ¨multiplication¨ by composition, but not a ring, since one distributive law and commutativity of multiplication fail; but A(T(D)) modulo bounded maps (much as in Mike´s description) is R. Steve Schanuel From rrosebru@mta.ca Wed Jan 12 15:17:08 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA28067 for categories-list; Wed, 12 Jan 2000 13:26:11 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f To: categories@mta.ca From: Lars Birkedal Subject: categories: Preprint: Elementary Axioms for Local Maps of Toposes Date: Wed, 12 Jan 2000 10:19:36 -0500 Message-ID: <5234.947690376@unbox.fox.cs.cmu.edu> Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Dear Category Theorists, We would like to inform you that our preprint Elementary Axioms for Local Maps of Toposes can be obtained electronically via http://www.cs.cmu.edu/afs/cs/Web/Groups/LTC/ or http://www.cs.cmu.edu/~birkedal Steven Awodey and Lars Birkedal. From rrosebru@mta.ca Thu Jan 13 18:21:57 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA19304 for categories-list; Thu, 13 Jan 2000 16:47:18 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Thu, 13 Jan 2000 18:59:59 +0100 (MET) From: Riccardo Focardi To: categories@mta.ca Subject: categories: Workshop on Issues in the Theory of Security (WITS '00) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: ==================================================== Apologies for multiple copies ==================================================== Call for Papers =============== Workshop on Issues in the Theory of Security (WITS '00) University of Geneva, Switzerland 7,8 July 2000 http://www.dsi.unive.it/IFIPWG1_7/wits2000.html Co-located with ICALP '00, the 27th International Colloquium on Automata, Languages, and Programming (9 to 15 July 2000) http://cuiwww.unige.ch/~icalp/ IMPORTANT DATES/DEADLINES: Submission of papers: 15 April 2000 Notification of acceptance: 31 May 2000 Workshop: 7,8 July 2000 OVERALL TOPIC AND FORMAT OF WORKSHOP: The IFIP WG 1.7 on "Theoretical Foundations of Security Analysis and Design" has been recently established to investigate the theoretical foundations of security, discovering and promoting new areas of application of theoretical techniques in computer security and supporting the systematic use of formal techniques in the development of security related applications. The members of WG will hold their annual workshop as an open event to which all researchers working on the theory of computer security are invited. The program will encourage discussions by all attendees, both during and after scheduled presentations on participants' ongoing work. Extended abstracts of work presented at the Workshop will be collected and distributed to the participants; no proceedings are foreseen for this year's workshop. POSSIBLE TOPICS FOR SUBMITTED PAPERS: Researchers are invited to submit abstracts of original work on topics in the spirit of the workshop. Possible topics for submitted papers include, but are not limited to: - formal definition and verification of the various aspects of security: confidentiality, integrity, authentication and availability; - new theoretically-based techniques for the formal analysis and design of cryptographic protocols and their manifold applications (e.g., electronic commerce); - information flow modelling and its application to the theory of confidentiality policies, composition of systems, and covert channel analysis; - formal techniques for the analysis and verification of mobile code; - formal analysis and design for prevention of denial of service. ORGANISING COMMITTEE: Pierpaolo Degano (chair) (Universita` di Pisa, I) Riccardo Focardi (Universita` di Venezia, I) Cathy Meadows (Naval Research Laboratory, USA) Paul Syverson (Naval Research Laboratory, USA) Joshua Guttman (Mitre, USA) SUBMISSION INSTRUCTIONS: Authors are invited to submit an extended abstract, 1-2 pages long, through the web. Instructions for electronic submissions can be found at the Workshop home page. Alternatively, they may e_mail a .ps file, or may mail a single copy of their paper to the program chair; in the last case, please allow ample time for delivery. Submissions should have the author's full name, address, fax number, e-mail address. VENUE: The workshop is co-located with the ICALP '00 conference, which will be held at the University of Geneva. Accommodations at a special ICALP rate have been reserved in a couple of hotels and very inexpensive rooms will be available at the Student Housing. Lunch will be served daily on campus and there will be morning and afternoon refreshment breaks. For more details see the ICALP '00 web address given above. CONTACT INFORMATION: Web: http://www.dsi.unive.it/IFIPWG1_7/wits2000.html Program chair: Pierpaolo Degano e-mail: degano@di.unipi.it telephone: +39 050 887257 fax: +39 050 887226 postal: Dipartimento di Informatica Universita' degli Studi di Pisa Corso Italia, 40 I-56125 PISA, Italia From rrosebru@mta.ca Fri Jan 14 11:47:10 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA10479 for categories-list; Fri, 14 Jan 2000 09:57:52 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <01BF5DEA.CBFAB980.noson@sci.brooklyn.cuny.edu> From: Noson Yanofsky Reply-To: "noson@sci.brooklyn.cuny.edu" To: "'categories@mta.ca'" Subject: categories: Preprint "The Syntax of Coherence" Date: Thu, 13 Jan 2000 17:22:40 -0500 Organization: Brooklyn College X-Mailer: Microsoft Internet E-mail/MAPI - 8.0.0.4211 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: The preprint "The Syntax of Coherence" is available on http://xxx.lanl.gov/abs/math.CT/9910006 Abstract: This article tackles categorical coherence within a two-dimensional generalization of Lawvere's functorial semantics. 2-theories, a syntactical way of describing categories with structure, are presented. From the perspective here afforded, many coherence results become simple statements about the quasi-Yoneda lemma and 2-theory-morphisms. Given two 2-theories and a 2-theory-morphism between them, we explore the induced relationship between the corresponding 2-categories of algebras. The strength of the induced quasi-adjoints are classified by the strength of the 2-theory-morphism. These quasi-adjoints reflect the extent to which one structure can be replaced by another. A two-dimensional analogue of the Kronecker product is defined and constructed. This operation allows one to generate new coherence laws from old ones. All the best, Noson S. Yanofsky From rrosebru@mta.ca Fri Jan 14 15:16:30 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA27735 for categories-list; Fri, 14 Jan 2000 13:28:25 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 14 Jan 2000 17:54:44 +0100 (MET) From: ig@liafa.jussieu.fr (Irene GUESSARIAN) Message-Id: <200001141654.RAA08221@liafa2.liafa.jussieu.fr> To: categories@mta.ca Subject: categories: FICS'2000 Call for Papers Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: FIXED POINTS IN COMPUTER SCIENCE (FICS 2000) July 22 and 23, 2000, Paris, France Call for Papers http://www.liafa.jussieu.fr/~ig/FICS.html * Fixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. 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 and logic communities who study or apply the fixed point operation in the different fields and formalisms. The First workshop on Fixed Points in Computer Science was held in Brno (1998). * Invited speakers: S. Bloom (Hoboken), B. Courcelle (Bordeaux), H. Marandjian (Yerevan), J. Rutten (Amsterdam), I. Walukiewicz (Warsaw). * PC chair: Irene Guessarian, LIAFA, University Paris 7, Paris 6, Case 7014, 2, place Jussieu, 75251 Paris Cedex 05, France e-mail: ig@liafa.jussieu.fr. * 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. * Paper submission: Authors are invited to send 3 copies of an abstract not exceeding 3 pages to the PC chair. Electronic submissions in the form of uuencoded postscript file are encouraged and can be sent to ig@liafa.jussieu.fr. Submissions are to be received before April 3, 2000. Authors will be notified of acceptance by June 1, 2000. * The workshop will be organised just before the Logic 2000 conference. From rrosebru@mta.ca Sat Jan 15 10:44:03 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA00112 for categories-list; Sat, 15 Jan 2000 09:48:23 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 14 Jan 2000 16:32:21 -0500 (EST) From: Peter Freyd Message-Id: <200001142132.QAA01366@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: squares and cubes Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: About an associative bifunctor I wrote There's a general theorem that says that a final coalgebra for X v X is automatically a final coalgebra for X v X v X v X, indeed, for any such ordered-wedge where the number of copies of X is a power of two. I haven't been able to find the proof for a general theorem that specializes to X v X v X. Well, the proof is just a modification of an old one (of mine). And once in hand, it makes clear the nonsensical nature of the construction for the thirding map that appeared in my "Derivatives" posting. (I'll replace it with a better construction in a later posting.) The general theorem is that if T is an endo-functor on a category with coproducts and if f:F --> TF is a final coalgebra then f Tfn F --> TF --> TTF is a final TT-coalgebra. (Citation below, albeit for the dual case -- it appears that not everyone has noticed that just by replacing the category in question with its dual one can transfer any theorem about initial algebras to one about final coalgebras.) Let X*Y denote the values of a bifunctor (not necessarily associative) on a category with binary coproducts. If f:F --> F*F is a final "square coalgebra" then f f*1 F --> F*F ----> (F*F)*F is a final "cubical coalgebra". Given a cubical coalgebra a:A --> (A*A)*A consider the square coalgebra A + A*A --> (A + A*A)*(A + A*A) whose left coordinate a r*l map is A --> (A*A)*A ----> (A + A*A)*(A + A*A) and whose right l*l coordinate map is A*A ----> (A + A*A)*(A + A*A) where l and r denote the left and right coprojections for the coproduct. Let A + A*A --> F be the induced map to the final square coalgebra and let a' and a'' be its coordinate maps. Then a' a'' A --------> F and A*A ------> F (add downward a | | f 1 | | f arrowheads) (A*A)*A -----> F*F A*A -----> F*F a''*a' a'*a' Consequently: a' A --------------> F a | | f a''*a' (A*A)*A ------------> F*F 1 | | f*1 (A*A)*A ---------> (F*F)*F (a'*a')*a' For the uniqueness, suppose that a' is as in the last diagram with the middle arrow removed. Define a'' so that the penultimate diagram commutes (f, by Lambek, is an isomorphism). Then the map from A + A*A to F whose coordinate maps are a' and a'' is a map of square coalgebras, hence a' is as already described. For a counterexample for arbitrary categories, consider the discrete category with two objects and bifunctor that turns it into the two-element group. On discrete categories coalgebras are, of course, the same as fixed points, and the only way a functor can have a final coalgebra is if it has a unique fixed point. The object that serves as the identity element for the group structure is thus the final square coalgebra. But both objects are cubical coalgebras, hence there is no final cubical coalgebra. There's nothing special about the number three. Given any iteration obtainable from the bifunctor, the constructions above can be modified to provide proofs and counterexamples. Indeed, we needn't restrict to bifunctors. For example, if TXYZ is a trifunctor on a category with binary coproducts, then a final coalgebra for TXXX gives rise to a final coalgebra for TX(T(TXXX)X)(TXX(TXXX)). But what I can't find a proof for is the analogue of this theorem, good for any category (same citation): If T is an endo-functor and if TT has a final coalgebra then so does T. The analogue would be: if X*Y is a bifunctor and if (X*X)*X has a final coalgebra then so does X*X. All my counterexamples -- here and in the citation below -- are on discrete categories. For what it's worth, if an associative bifunctor on a discrete category is such that X*X*X has a final coalgebra, then so does X*X. Algebraically Complete Categories, Como Conference, Category Theory, Proceedings of the International Conference held in Como, Italy, 1990, Lecture Notes in Mathematics, 1488, Springer-Verlag, 1991 From rrosebru@mta.ca Sun Jan 16 12:22:36 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA29488 for categories-list; Sun, 16 Jan 2000 11:29:14 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <388158B3.60AF9957@kestrel.edu> Date: Sat, 15 Jan 2000 21:35:47 -0800 From: Dusko Pavlovic X-Mailer: Mozilla 4.5 [en] (X11; U; SunOS 5.5.1 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: CATEGORIES mailing list Subject: categories: Re: squares and cubes Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: hi. i somehow managed to unsubscribe from this list at some point, and almost missed the thread about coalgebra of reals. i am not sure that i have seen all the relevant postings, but here are my 2p of thoughts. if i am not misunderstanding anything, peter freyd's closed interval coalgebra achieves something that vaughan pratt's and mine do not. we work with lists and streams and get *irredundant* representations of reals. however, without redundancy, the algebraic operations on reals are undecidable. peter's bipointed approach, however, induces a *redundant* representation. this allows him to extract the algebraic operations coinductively. in the talk at the 1998 lisbon workshop on coalgebra (and later in some seminar talks), i described a redundant coalgebra of conway reals, where conway's definitions of the field operations were derivable as coalgebra homomoprhisms. however, the setting seemed too complicated, probably due to me. peter's definition of the midpoint algebra is considerably simpler, although the resulting operations are probably still computationally quite inefficient. the coalgebra of alternating dyadics, described in the paper with vaughan, was derived from this 'conway' coalgebra. as explained in sec 3.4, it provides the best dyadic approximation, while the continued fraction coalgebra, provides the best rational approximation. presumably, it can be derived from the 'norton' coalgebra (contorted fractions), mentioned by peter johnstone. there are as many redundant coalgebras of reals, as there are corresponding irredundant ones (one for every interval partition), for fast outputs. i think that some of the mentioned *mysteries* about the maps between these various representations boil down to the fact that they are coalgebra isomorphisms, that do not preserve the derived structure, but rather *transform* it. eg, the laplace transform is a coalgebra isomorphism between the coalgebra of analytic functions and a dual coalgebra of meromorphic functions --- whereby the convolution ring gets transformed into a multiplicative domain, etcetc. in any case, when you are done with reals, you may be interested to have a look int my paper with martin escardo "calculus in coinductive form", LICS98, or ftp://ftp.kestrel.edu/pub/papers/pavlovic/LAPL.ps.gz all the best, -- dusko PS along the lines of peter's bipointed construction (and also to check whether i understood it): * bipointed sets are the algebras for the functor 2+(-) : Set -> Set. * bipointed sets with two _distinct_ points are the free such algebras. so lets work in the kleisli category *K* for 2+(-). write 2 = {0,1} * the bifunctor (-) v (-) : *K* --> *K* maps * the objects X, Y to X + {m} + Y * the arrows X --f-->2+U and Y--g-->2+V to h : X+{m}+Y ---> 2 + U+{m}+V h(x) = f(x) if f(x) = 0 or f(x) in U h(x) = m if f(x) = 1 h(M) = m h(y) = g(y) if g(y) = 1 or g(y) in V h(y) = m if g(y) = 0 * now (0,1) is the final coalgebra for the functor X v X on *K*. the coalgebra structure (0,1) ---> 2+(0,1) +{m}+(0,1) maps 1/2 to m, x<1/2 to 2x and x>1/2 to 2x-1. * the finality is now easy to prove directly, by displaying the anamorphism for any given coalgebra X -r-> 2+X+{m}+X. ditto for the algebraic structure. From rrosebru@mta.ca Sun Jan 16 12:57:40 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA23199 for categories-list; Sun, 16 Jan 2000 11:17:03 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sat, 15 Jan 2000 13:07:11 -0500 (EST) From: Peter Freyd Message-Id: <200001151807.NAA10666@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Addendum Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Sorry for the clutter. I forgot a counterexample. Yes, it is possible for (X*X)*X to have a final coalgebra but not X*X. On the discrete category with two objects, A and B, let the bifunctor be defined by: * | A B --+------ A | B A B | A A The unique cubical coalgebra is A but there is no square coalgebra. What I don't have is a counterexample with an _associative_ bifunctor. From rrosebru@mta.ca Mon Jan 17 14:08:32 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA22267 for categories-list; Mon, 17 Jan 2000 09:48:13 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001170545.VAA03567@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: squares and cubes In-reply-to: Your message of "Sat, 15 Jan 2000 21:35:47 PST." <388158B3.60AF9957@kestrel.edu> Date: Sun, 16 Jan 2000 21:45:50 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: From: Dusko Pavlovic >if i am not misunderstanding anything, peter freyd's closed interval >coalgebra achieves something that vaughan pratt's and mine do not. we work >with lists and streams and get *irredundant* representations of reals. >however, without redundancy, the algebraic operations on reals are >undecidable. peter's bipointed approach, however, induces a *redundant* >representation. this allows him to extract the algebraic operations >coinductively. I am deeply embarrassed at not drawing this inference myself. I noticed the felicitous identification of 0111... and 1000... but the importance of the resulting redundancy didn't click. That the whole process happened in one step led me to think that the representation was as irredundant as all extant one-step constructions. The fact that addition is easier to define with Peter's functor than with ours should have been a big hint. Redundant representations for fast computer arithmetic have been in wide use since the 1960's. The Wallace tree, long available in chip form, leverages the idea to multiply n bit integers with log n circuit delay. (Chris Wallace is an Australian computer scientist who came up with this idea while working on Illiac 2 at the University of Illinois.) The actual multiplication takes half the time, the other half is spent performing the identification step at the end, namely by putting the result into canonical form. All redundant representations of the reals that are or could be used in computer architecture require a separate step to identify the redundant representations. For example Schanuel's recently discussed almost-additive sequences of integers redundantly represent the reals, and must be quotiented in order to represent them irredundantly. By the same token the group of bounded sequences that I mentioned does the same, and it too must be quotiented in a separate step, in this case by a subgroup expressing 2(x/2) = x. Peter's final coalgebra performs the identification in the same step in which the reals are created. I am fairly confident there is no precedent for such a one-step construction of the reals in which the representation is redundant. Vaughan Pratt From rrosebru@mta.ca Mon Jan 17 14:10:06 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA13687 for categories-list; Mon, 17 Jan 2000 10:41:56 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001170637.WAA03764@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Addendum In-reply-to: Your message of "Sat, 15 Jan 2000 13:07:11 EST." <200001151807.NAA10666@saul.cis.upenn.edu> Date: Sun, 16 Jan 2000 22:37:40 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > * | A B > --+------ > A | B A > B | A A > >The unique cubical coalgebra is A but there is no square coalgebra. > >What I don't have is a counterexample with an _associative_ bifunctor. How about the positive integers with * as sum, with 1->3 as the only nonidentity arrow? The unique cubical coalgebra is 1 but there is no square coalgebra. Vaughan From rrosebru@mta.ca Mon Jan 17 14:36:56 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA18182 for categories-list; Mon, 17 Jan 2000 10:41:20 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001170545.VAA03567@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: squares and cubes In-reply-to: Your message of "Sat, 15 Jan 2000 21:35:47 PST." <388158B3.60AF9957@kestrel.edu> Date: Sun, 16 Jan 2000 21:45:50 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: From: Dusko Pavlovic >if i am not misunderstanding anything, peter freyd's closed interval >coalgebra achieves something that vaughan pratt's and mine do not. we work >with lists and streams and get *irredundant* representations of reals. >however, without redundancy, the algebraic operations on reals are >undecidable. peter's bipointed approach, however, induces a *redundant* >representation. this allows him to extract the algebraic operations >coinductively. I am deeply embarrassed at not drawing this inference myself. I noticed the felicitous identification of 0111... and 1000... but the importance of the resulting redundancy didn't click. That the whole process happened in one step led me to think that the representation was as irredundant as all extant one-step constructions. The fact that addition is easier to define with Peter's functor than with ours should have been a big hint. Redundant representations for fast computer arithmetic have been in wide use since the 1960's. The Wallace tree, long available in chip form, leverages the idea to multiply n bit integers with log n circuit delay. (Chris Wallace is an Australian computer scientist who came up with this idea while working on Illiac 2 at the University of Illinois.) The actual multiplication takes half the time, the other half is spent performing the identification step at the end, namely by putting the result into canonical form. All redundant representations of the reals that are or could be used in computer architecture require a separate step to identify the redundant representations. For example Schanuel's recently discussed almost-additive sequences of integers redundantly represent the reals, and must be quotiented in order to represent them irredundantly. By the same token the group of bounded sequences that I mentioned does the same, and it too must be quotiented in a separate step, in this case by a subgroup expressing 2(x/2) = x. Peter's final coalgebra performs the identification in the same step in which the reals are created. I am fairly confident there is no precedent for such a one-step construction of the reals in which the representation is redundant. Vaughan Pratt From rrosebru@mta.ca Mon Jan 17 14:44:43 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA30054 for categories-list; Mon, 17 Jan 2000 09:47:16 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Peter Selinger Message-Id: <200001170123.UAA13135@liberty.math.lsa.umich.edu> Subject: categories: Re: Real midpoints To: categories@mta.ca (Categories List) Date: Sun, 16 Jan 2000 20:23:36 -0500 (EST) In-Reply-To: <199912261845.NAA19441@saul.cis.upenn.edu> from "Peter Freyd" at Dec 26, 1999 01:45:08 PM X-Mailer: ELM [version 2.5 PL1] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Dusko Pavlovic wrote on Jan 15: > peter's bipointed approach, however, induces a *redundant* > representation. this allows him to extract the algebraic operations > coinductively. Sorry for lagging a few weeks behind in this discussion. Something has been bothering me about Peter's definition of the midpoint operation (Dec 26). How can it be coinductive, but the resulting function is not computable? After mulling it over, I realized that Peter's definition is *not* coinductive: He gives an equation which has a unique fixpoint, but it is not a coinductive fixpoint. I believe that Peter's representation has not enough redundancy to define the algebraic operations in a purely coinductive manner. Note however that Peter really only wanted to define the algebraic structure from the final coalgebra structure on I = [-1,1]; he did not claim to do it purely coinductively. Recall Peter's definition of the midpoint operation (where h:I-->I is the "halfing" map h(x) = x|0). I have corrected some typos in lines 4+5: > Let g be the endo-function on I x I defined recursively by: > > g = if dx = T and dy = T then else > if dx = T and uy = B then (h x h) (g) else > if ux = B and dy = T then (h x h) (g) else > if ux = B and uy = B then . > > The values of g lie in the first and third quadrants, that is, those > points such that either dx = dy = T or ux = uy = B. The two maps > > g d x d g u x u > I x I --> I x I --> I x I and I x I --> I x I --> I x I > > give a coalgebra structure on I x I. The midpoint operation may be > defined as the induced map to the final coalgebra. I think Vaughan has already pointed out that this is not well-defined, because the four cases in the definition of g are not mutually disjoint and the right-hand sides do not match; thus let us assume we write "dx != T" instead of "ux = B", and similarly for y. Note that the resulting map is neither continuous nor monotone; thus, we are definitely forced to work with bipointed sets, not posets, for this construction. My point is that the definition of g is neither recursive nor co-recursive. The definition of g is merely expressed as a fixpoint equation, and Peter has set up things so that there is indeed a unique solution to this equation. However, the reason the fixpoint is unique is because the "h" part is contracting, and not because the equation is co-recursive. If we write g as a pair : I x I --> I, we can separate the equation for g into two equations about g1 and g2. A priori, these two equations are mutually dependent, but interestingly, it turns out that they are independent, so we need not worry about simultaneous fixpoints. The equation for g1 can be written as s x s dist I x I -------> (I + I) x (I + I) ------> IxI + IxI + IxI + IxI | | (1) | g1 | pi1 + g1 + g1 + pi1 | | [h-,h,h,h+] I <---------------------------------- I + I + I + I (add downward arrow heads), where s: I --> I v I --> I + I is the composition of the coalgebra morphism F for I with one of the two obvious maps I v I --> I + I (the one that sends the midpoint to the second component, say). "dist" is distributivity, and h- and h+ are the maps defined by h-(x) = x|-1 and h+(x) = x|1 (these have explicit definitions similar to that of the halfing map h). The equation for g2 is similar. One obtains it by replacing pi1 with pi2. For this diagram to be considered a co-recursive definition of g1, it would have to be equivalent to a diagram of the form G I x I ---------------> (I x I) v (I x I) | | (2) | g1 | g1 v g1 | | F I ---------------------> I v I for some suitable coalgebra G on I x I. This, however, is not the case, unless (in a suitable sense) G is just as complex as g1 is. For instance, the first bit (trit?) of G(x,y) is the same as that of g(x,y), which is the same as the first bit of midpoint(x,y). But the first bit of the midpoint cannot be computed with finite lookahead (consider x = 1/3 = +-+-+-... and y = -1/3 = -+-+-+...). Thus, the first bit of g or G can't be computed either, and no matter through how many levels of co-recursion we go, we never arrive at an elementary function. Thus, there is no chance of defining the midpoint operation from elementary functions through a finite chain of co-recursions. It ought to be possible to formalize this argument. Intuitively, note that in diagram (2), g1 appears in something like a "tail recursive" position, whereas in diagram (1) it does not. Thus, if G is computable with finite lookahead (as a function on pairs of streams), and g1 is defined like in (2), then g1 is also computable with finite lookahead: namely, G will tell us the first trit, plus a continuation, and the tail recursive call will compute the rest. Thus computable functions on streams are closed under co-recursion (as they should). Finally, Peter's definition of the midpoint function utilizes the function g and then lifts it through one level of co-recursion. It is, however, possible, to define the midpoint function directly without going through this g: It is the unique morphism m: I x I --> I that makes the following diagram commute: s x s dist I x I -------> (I + I) x (I + I) ------> IxI + IxI + IxI + IxI | | (1) | m | m + m + m + m | | [h-,h,h,h+] I <---------------------------------- I + I + I + I. Or, if you prefer, it is the unique solution of m = if dx = T and dy = T then h+ (m) else if dx = T and dy != T then h (m) else if dx != T and dy = T then h (m) else if dx != T and dy != T then h- (m) This definition, of course, is not co-recursive either. If I am not mistaken, it is more or less what Vaughan defined in his mail on Dec 24, except he separated the case for dx = T into two cases ux != B and (dx=T and ux=B) (and similarly for y). Best wishes, -- Peter Selinger From rrosebru@mta.ca Tue Jan 18 10:24:34 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA07563 for categories-list; Tue, 18 Jan 2000 09:00:40 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001172118.NAA06734@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Addendum In-reply-to: Your message of "Sun, 16 Jan 2000 22:37:40 PST." <200001170637.WAA03764@coraki.Stanford.EDU> Date: Mon, 17 Jan 2000 13:18:18 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: >How about the positive integers with * as sum, with 1->3 as the only >nonidentity arrow? The unique cubical coalgebra is 1 but there is no >square coalgebra. Oops, that gets associativity at the cost of * no longer being a functor (pointed out to me by Peter Selinger). Ok, let me dig myself in deeper by making my example more complicated. Instead of 1->3, put an arrow from i to j whenever i <= j <= 2i. Now every i is a square coalgebra but no i is a cubical coalgebra. Now adjoin a new object oo (infinity), with x+oo = oo+x = oo for all x, and the identity at oo as the only new arrow. oo is both a square *and* a cubical coalgebra. Since it is disconnected from the other square coalgebras there can't be a final such. But oo is the only cubical coalgebra, with only one self-map, making it a final cubical coalgebra. Vaughan From rrosebru@mta.ca Tue Jan 18 10:24:36 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA04610 for categories-list; Tue, 18 Jan 2000 09:02:30 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <3883E700.797D12A9@kestrel.edu> Date: Mon, 17 Jan 2000 20:07:28 -0800 From: Dusko Pavlovic X-Mailer: Mozilla 4.5 [en] (X11; U; SunOS 5.5.1 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: Peter Selinger CC: Categories List Subject: categories: Re: Real midpoints References: <200001170123.UAA13135@liberty.math.lsa.umich.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > My point is that the definition of g is neither recursive nor > co-recursive. The definition of g is merely expressed as a fixpoint > equation, and Peter has set up things so that there is indeed a unique > solution to this equation. However, the reason the fixpoint is unique > is because the "h" part is contracting, and not because the equation > is co-recursive. what exactly do you mean by corecursive? (it's guarded, and guarded equations do have unique fixpoints.) -- dusko From rrosebru@mta.ca Tue Jan 18 10:33:33 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA03480 for categories-list; Tue, 18 Jan 2000 09:03:03 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Subject: categories: Re: Addendum To: pratt@cs.stanford.edu (Vaughan Pratt) Date: Tue, 18 Jan 100 09:49:42 +0000 (GMT) Cc: categories@mta.ca In-Reply-To: <200001170637.WAA03764@coraki.Stanford.EDU> from "Vaughan Pratt" at Jan 16, 0 10:37:40 pm X-Mailer: ELM [version 2.4 PL25] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-Id: From: "Dr. P.T. Johnstone" Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > How about the positive integers with * as sum, with 1->3 as the only > nonidentity arrow? The unique cubical coalgebra is 1 but there is no > square coalgebra. Doesn't sound very functorial to me. Peter Johnstone From rrosebru@mta.ca Tue Jan 18 10:34:07 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA07492 for categories-list; Tue, 18 Jan 2000 09:01:44 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001180057.QAA07887@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: squares and cubes In-reply-to: Your message of "Sun, 16 Jan 2000 21:45:50 PST." <200001170545.VAA03567@coraki.Stanford.EDU> Date: Mon, 17 Jan 2000 16:57:47 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: >I am deeply embarrassed at not drawing this inference myself. I noticed >the felicitous identification of 0111... and 1000... but the importance of >the resulting redundancy didn't click. That the whole process happened >in one step led me to think that the representation was as irredundant >as all extant one-step constructions. The fact that addition is easier >to define with Peter's functor than with ours should have been a big hint. Well, maybe not so embarrassed after all. Although there is some redundancy, as Peter Selinger pointed out to me (in the same message where he pointed out the problem with 1->3) there isn't enough redundancy to make the function constituting Peter F.'s midpoint coalgebra computable, at least not corecursively. Given say -++---+-++... and +--+++-+--... (two complementary reals x and -x, which must therefore sum to zero), if they stay complementary forever one can output either of +---------... or -+++++++++... forever, with one output bit per input bit. These two infinite sequences redundantly represent zero (as does the empty sequence). Furthermore if one pictures oneself as outputting both infinite sequences (justified by the idea that in the limit they become the same real), then one can discard the "wrong" one when it is discovered that the two inputs aren't complementary. Addition defined corecursively in this way is effective. But while this is computationally appealing, technically speaking it isn't quite coinduction, which makes no provision for hedging one's bets by carrying along both possibilities when you can't make up your mind. To make traditional redundant computer arithmetic work coinductively, more redundancy is needed. To that end I tried tripointed sets, calling the constants -,0,+, along with a functor 3(X) that makes not two but three copies of X and pastes their constants together as follows: - 0 + - 0 + - 0 + ------------- - . 0 . + The idea is that the constants denote -1, 0, and 1 respectively and that 3(I) somehow is isomorphic to I, with the two dots becoming -1/2 and 1/2 respectively. But for that to work 3(-) would have to paste a lot more points than it does. So this seems like a nice question: is there a category C and a functor F:C->C whose final coalgebra is the continuum with sufficiently redundant coalgebraic structure to permit addition to be defined coinductively? Vaughan From rrosebru@mta.ca Wed Jan 19 12:42:27 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA16291 for categories-list; Wed, 19 Jan 2000 10:32:44 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001181947.LAA13699@coraki.Stanford.EDU> To: categories@mta.ca Subject: categories: Re: Addendum In-reply-to: Your message of "Mon, 17 Jan 2000 13:18:18 PST." <200001172118.NAA06734@coraki.Stanford.EDU> Date: Tue, 18 Jan 2000 11:47:41 -0800 From: Vaughan Pratt Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > Instead of 1->3, put an arrow from i to j whenever i <= j <= 2i. I keep forgetting to make a list of what to remember. Peter Johnstone kindly put me out of my misery on this noncategory. Since I don't seem to be having much luck making the example more complicated, maybe making it simpler might work. The ring of integers mod 3 is a one-object monoidal category in the usual way, with multiplication as composition and addition as the monoid. Every arrow is clearly both a square coalgebra and a cubical coalgebra, i.e. we have three of each. Claim: There are no final square coalgebras, but 1 and 2 are final cubical coalgebras. Proof. Square coalgebra homomorphisms f from 2x to x (as square coalgebras) are those that satisfy xf = (2f)(2x). But 2x2 = 1 (mod 3) so every f solves this. Hence there are three square coalgebra homomorphisms from 2x to x, whence no x is a final square coalgebra. Cubical coalgebra homomorphisms f from y to x (as cubical coalgebras) must satisfy xf = (3f)y = 0. But for x other than 0, f = 0 is the only solution. So the two nonzero cubical coalgebras are final. The same example (unless I've forgottten yet another thing) solves the corresponding problem for initial algebras. Vaughan From rrosebru@mta.ca Wed Jan 19 12:48:57 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA19930 for categories-list; Wed, 19 Jan 2000 10:43:55 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 18 Jan 2000 10:14:32 -0500 (EST) From: Peter Freyd Message-Id: <200001181514.KAA13738@saul.cis.upenn.edu> Subject: categories: Addendum squared or cubed, depending on what you count. To: categories@mta.ca Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Vaughan writes: How about the positive integers with * as sum, with 1->3 as the only nonidentity arrow? The unique cubical coalgebra is 1 but there is no square coalgebra. Indeed, but there's no _final_ cubical coalgebra. What I don't have is a category with an associative bifunctor with a final cubical coalgebra but no final square coalgebra. On a _discrete_ category being the unique coalgebra is necessary and sufficient for being a final coalgebra. It's easy to see that in a semigroup if x is a unique solution to xxx = x then x is the unique solution to xx = x. After writing all that, I note that in Vaughan's example, * is not a functor. If it were, there would have to map from 1*1 to 1*3 and 1*1 would be a square coalgebra. From rrosebru@mta.ca Wed Jan 19 12:50:29 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA16409 for categories-list; Wed, 19 Jan 2000 10:33:23 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Mailer: exmh version 2.0.2 2/24/98 To: categories@mta.ca, bra-types@cs.chalmers.se, concurrency@cwi.nl, eacsl@dimi.uniud.it, types@cis.upenn.edu cc: paiva@parc.xerox.com, pratt@cs.stanford.edu Subject: categories: LICS Workshop on Chu Spaces and Applications 25th June 2000, CA Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii From: Valeria Correa Vaz de Paiva Message-Id: <00Jan18.121108pdt."79834"@panini.parc.xerox.com> Date: Tue, 18 Jan 2000 12:11:36 PST Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: CALL FOR PAPERS LICS'2000 Workshop on Chu Spaces: Theory and Applications Sunday, June 25, 2000, Santa Barbara, California http://www.cs.bham.ac.uk/~vdp/chu.html A Chu space is a related pair of complementary objects. Besides having intrinsic interest in their own right, Chu spaces have found applications to concurrent processes, information flow, linear logic, proof theory, and universal categories. The workshop is concerned with the theory and applications of Chu spaces, as well as related structures such as the Dialectica construction and double glueing. The workshop will bring together computer scientists, mathematicians, logicians, philosophers, and other interested parties to discuss the development of the subject with regard to its foundations, applications, prospects, and directions for future work. Work in the subject is currently fragmented across several areas: category theory, traditional model theory, concurrency, and the semantics of programming languages, and such a workshop can contribute to the coordination and possibly even some unification of these efforts. Suggested topics for presentation and discussion include but are by no means limited to new results about Chu spaces and related structures; their applications to various areas such as concurrency, games, proof theory, etc.; and their implications for foundations and philosophy of computation, mathematics, physics, and other disciplines. The workshop will be held on Sunday, June 25, 2000 at Santa Barbara, California, as an adjunct to the International Conference on Logic in Computer Science (LICS'2000), June 26-29 at the same location as per http://www.cs.bell-labs.com/who/libkin/lics/index.html. Papers within the scope of the workshop are solicited, and may be either work in progress or more mature work. Submission should be in the form of an extended abstract of at most 10 pages, in postscript format, mailed electronically to paiva@parc.xerox.com. Submissions will be evaluated by a committee selected by the organizers, and the full version of accepted papers will be printed in a proceedings available at the start of the workshop. Important dates: Extended abstract: April 25, 2000 Notification of acceptance: May 15, 2000 Proceedings version: June 9, 2000 The workshop will be one full day and is open to all interested researchers. Valeria de Paiva paiva@parc.xerox.com Vaughan Pratt pratt@cs.stanford.edu http://www.cs.bham.ac.uk/~vdp/chu.html From rrosebru@mta.ca Wed Jan 19 12:51:13 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA15473 for categories-list; Wed, 19 Jan 2000 10:31:48 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Peter Selinger Message-Id: <200001181616.LAA27249@liberty.math.lsa.umich.edu> Subject: categories: Re: Real midpoints To: categories@mta.ca (Categories List) Date: Tue, 18 Jan 2000 11:16:22 -0500 (EST) In-Reply-To: <3883E700.797D12A9@kestrel.edu> from "Dusko Pavlovic" at Jan 17, 2000 08:07:28 PM X-Mailer: ELM [version 2.5 PL1] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > > My point is that the definition of g is neither recursive nor > > co-recursive. The definition of g is merely expressed as a fixpoint > > equation, and Peter has set up things so that there is indeed a unique > > solution to this equation. However, the reason the fixpoint is unique > > is because the "h" part is contracting, and not because the equation > > is co-recursive. Dusko Pavlovic wrote: > what exactly do you mean by corecursive? (it's guarded, and guarded equations > do have unique fixpoints.) The definition I had in mind is that an arrow g is defined from G by co-recursion "in a single step" if it arises as the unique coalgebra homomorphism from a coalgebra G to the terminal coalgebra. It is defined by co-recusion "in multiple steps" if it is obtained from certain basic morphisms by repeated applications of the above single step, together with basic operations on morphisms. I am not so sure what I mean by "basic"; but I have in mind morphisms and operations that are defined by ordinary equations (as opposed to fixpoint equations) from the structure of the category at hand (such as composition, pairing, the functor "X v Y", etc). What's the exact definition of "guarded" in this context? I assume that h x h would be the guard. The fact that Peter's equation has a unique fixpoint relies on the fact that h x h is contracting. It follows, for instance, from Banach's fixpoint theorem. If one omits the "h x h", there are multiple fixpoints. It seems that the proof that Peter's equation has a unique fixpoint is independent of the underlying representation of [0,1], whereas my proposed definition of "co-recursive" is not. By the way, Peter's definition of the "halfing" map does not quite fit my idea of a "basic" map above: > Let F:I --> I v I be a final coalgebra. We will denote the top of I > as T and the bottom as B. Construct the "halving" map, h:I --> I, > (on [-1,1] it will send x to x/2) as: > > T v F v B F'v F' F' > I --> 1 v I v 1 ------> I v I v I v I ---> I v I --> I > > where F' denotes the inverse of F, and, by a little overloading, T > and B denote the maps constantly equal to T and B. The leftmost > map records the fact that the terminator is a unit for the > ordered-wedge functor. The problem is that "X v Y" is only functorial on morphisms that preserve top and bottom, and neither T nor B are of that form. Thus it seems one needs to briefly step outside the category to justify this particular definition of h. -- Peter From rrosebru@mta.ca Wed Jan 19 14:43:16 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA14113 for categories-list; Wed, 19 Jan 2000 10:28:23 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 18 Jan 2000 09:52:40 -0500 (EST) From: Peter Freyd Message-Id: <200001181452.JAA12681@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: deeper and deeper Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Vaughan writes Ok, let me dig myself in deeper by making my example more complicated. Instead of 1->3, put an arrow from i to j whenever i <= j <= 2i. Now ever y i is a square coalgebra but no i is a cubical coalgebra. There's an arrow from 1 to 2 but none from 1*1 to 1*2. And when put back in you'll obtain an arrow from 1 to 3. Even without associativity, if A is a X*X coalgebra then A is an (X*X)*X coalgebra. From rrosebru@mta.ca Wed Jan 19 15:11:40 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA06024 for categories-list; Wed, 19 Jan 2000 13:30:50 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <000c01bf622e$0ddd7c60$80213018@buf.adelphia.net> From: "Stephen H. Schanuel" To: Cc: "Stephen H Schanuel" Subject: categories: Reals a la Eudoxus (updated from re: Tate Reals) Date: Tue, 18 Jan 2000 22:34:10 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: My 'construction' of the reals, referred to by Ross and Mike, was suggested by an observation of Tate about bilinear maps many years earlier, but essentially goes back to Eudoxus, who noted that to measure the ratio of a line segment to another with any desired accuracy, it isn't necessary to cut either of them up--instead multiply the 'numerator' segment by a large integer--thus pointing the way to a direct construction of the reals as ring from the integers as mere additive group. (Incidentally, I take the task to be relating the continuous to the discrete, rather than constructing the former from the latter, but never mind.) R is the ring of endomorphisms E(T(L))of the group T(L) of translations (rigid maps at finite distance from the identity) of the line L. If we start instead with a discrete line D (a line of dots), then T(D) is isomorphic to Z (additive group without preferred generator). E(T(D) is the ring Z, but instead take A(T(D)), 'almost homomorphisms' (as in Mike's description) from Z to Z. A(T(D)) is an additive goup with a 'multiplication' by composition, but not a ring, since one distributive law and commutativity of multiplication fail; but A(T(D)) modulo bounded maps is R. The maps in both directions are easy: send the real r to the map 'multiply by r and round down', and send the almost homomorphism f to the limit of the Cauchy sequence f(n)/n. Steve Schanuel From rrosebru@mta.ca Wed Jan 19 15:18:21 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA05422 for categories-list; Wed, 19 Jan 2000 13:27:19 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Wed, 19 Jan 2000 11:03:38 -0500 (EST) From: Peter Freyd Message-Id: <200001191603.LAA28124@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: 1 = 2? Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Vaughan writes: The ring of integers mod 3 is a one-object monoidal category in the usual way, with multiplication as composition and addition as the monoid. A monoid -- as does any functor on two variables -- has to carry identity maps into identity maps. If composition is multiplication then 1 is the identity map. But if * is addition then 1*1 ... From rrosebru@mta.ca Wed Jan 19 19:13:12 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA01548 for categories-list; Wed, 19 Jan 2000 16:38:35 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Wed, 19 Jan 2000 14:57:34 -0500 (EST) From: Peter Freyd Message-Id: <200001191957.OAA24217@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: thirding Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Let S and C be endo-functors that commute, that is, there's a natural equivalence c:CS --> SC. If f: F -> SF is a final S-coalgebra then there a special map CF --> F, to wit, the induced Cf c_F coalgebra map from the S-coalgebra CF --> CSF --> SCF. Now specialize to the case that SX is X*X for an associative bifunctor and CX is X*X*X. Indeed, specialize further to the case that * is the ordered-wedge functor so that F is the closed interval, I. In this special case the induced map I v I v I --> I is an isomorphism and its inverse makes I a final cubical coalgebra. I don't know a general theorem that specializes to this result. Clearly I v I v I --> I can be used to obtain the thirding map on the interval that I needed for my definition of derivatives. And clearly there's nothing special about the number three. We obtain a special isomorphism from every iterated ordered-wedge of I back to I. In that previous posting on derivatives I wrote: Using that the closed interval is the final coalgebra for X v X v X we can define the thirding map t:I --> I in a manner similar to (and simpler than) the definition of the halving map. The problem, of course, was that there was no control on _which_ final cubical coalgebra structure was to be used. From rrosebru@mta.ca Wed Jan 19 20:33:00 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA12463 for categories-list; Wed, 19 Jan 2000 19:19:25 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Wed, 19 Jan 2000 16:16:41 -0500 (EST) From: Peter Freyd Message-Id: <200001192116.QAA27262@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Midpoint Algebras Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: I've defined the theory of midpoint algebras to be given by a single binary operator satisfying the three equations; x|x = x Idempotence; x|y = y|x Commutativity; (u|v)|(x|y) = (u|x)|(v|y) Middle-two interchange; and the Horn sentence: x|y = x|z => y = z Cancelation. For a non-Euclidean example choose a subset of the circle consisting of an oddly finite number of evenly placed points ("evenly placed" meaning that the distances between any point and its two immediate neighbors are the same). For any two points we take their midpoint to be the unique point that's equally distant from the two of them. I'll call this a cyclic midpoint algebra. There's one isomorphism type for each odd natural number. And there aren't too many other finite midpoint algebras: 1. Any non-empty finite midpoint algebra is isomorphic to a product of cyclic midpoint algebras each of prime-power order. (In particular, there are no finite midpoint algebras of even order.) A little theorem that I find quite annoying: 2. The finite midpoint algebras are semantically complete with respect to the Horn theory. That is, the universally quantified first-order Horn sentences on the predicate x|y = z that hold for all cyclic midpoint algebras hold for all midpoint algebras. It's annoying because the finite examples are so unlike the motivating example of Euclidean space. (Note the perversity: the midpoint of a pair of adjacent points on a cyclic midpoint algebra is maximally far from each of them.) An algebra (for any theory) is said to be torsion-free if the only finite subalgebras are those with just one element. Torsion freeness is always given by a Horn theory. For midpoint algebras, torsion freeness can be specified with the sequence of Horn sentences of the form: x = y|(y|(y|(...(y|(y|x))...))) => x = y I little theorem that I don't find at all annoying: 3. The real line is semantically complete with respect to the universal quantified first-order theory of torsion-free midpoint algebras. Because: 1: Given a non-empty finite midpoint algebra choose an element and label it 0. Define the halving function h by hx = 0|x. The cancelation condition says that h is injective, therefore a permutation. Define x+y by h(x+y) = x|y and verify the abelian group axioms. The decomposition theorem for finite abelian groups finishes the proof. 2: Given an arbitrary non-empty midpoint algebra we may, as observed in my first post on this subject, choose a 0 and obtain a larger algebra in which the halving map becomes an automorphism. (It may be explicitly constructed as the set whose elements are named by pairs where x is an element in the given algebra and n is a natural number; names the same element iff h^m(x) = h^n(y); midpoints are defined by | = .) Define x+y as above to obtain a commutative monoid with the cancelation property and apply the classical construction to obtain a larger commutative monoid that is an abelian group. Note that this group has unique division by two, hence we may view it as a module over the ring, D, of dyadic rationals. Given a Horn sentence with a counterexample in some midpoint algebra we seek a counterexample in a cyclic midpoint algebra. The given counterexample consists of a finite number of elements. If we embed their ambient midpoint algebra into a D-module, we may cut down to the submodule generated therein by the image of those elements to obtain a finitely generated D-module. One may easily verify that D is a principal ideal domain, hence this last D-module decomposes as a direct sum of cyclic D-modules. The indecomposable cyclic modules correspond to the prime-powers in D, that is, there are finite cyclic groups of odd (ordinary) prime power order (each automatically a D-module) and one infinite case, D itself, viewed as a D-module. For the finite set of elements to constitute a counterexample we need to maintain one given non-equation, hence we can land in a cyclic D-module. If it happens to be the infinite cyclic D-module, factor out by a principal ideal generated by a sufficiently large prime integer to maintain the non-equation. 3. Given a counterexample to a universally quantified first-order sentence in a torsion-free midpoint algebra repeat the above construction to obtain a counterexample in a finite direct sum of cyclic D-modules. Verify that it remains a counterexample when we factor out the torsion submodule -- that is, verify that the map from the original torsion-free midpoint algebra remains an embedding. We now have a counterexample in a finite direct sum of copies of D. Enlarge to a finite direct sum of copies of the rational numbers. One does not even need the axiom of choice to embed finite-dimensional rational vector spaces into the one-dimensional real space. From rrosebru@mta.ca Wed Jan 19 20:33:42 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA01309 for categories-list; Wed, 19 Jan 2000 16:37:33 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <38861D2D.8BA95CD5@kestrel.edu> Date: Wed, 19 Jan 2000 12:23:09 -0800 From: Dusko Pavlovic X-Mailer: Mozilla 4.5 [en] (X11; U; SunOS 5.5.1 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: Categories List Subject: categories: Re: Real midpoints References: <200001181616.LAA27249@liberty.math.lsa.umich.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: > > what exactly do you mean by corecursive? (it's guarded, and guarded equations > > do have unique fixpoints.) > > The definition I had in mind is that an arrow g is defined from G by > co-recursion "in a single step" if it arises as the unique coalgebra > homomorphism from a coalgebra G to the terminal coalgebra. It is > defined by co-recusion "in multiple steps" if it is obtained from > certain basic morphisms by repeated applications of the above single > step, together with basic operations on morphisms. I am not so sure > what I mean by "basic"; but I have in mind morphisms and operations > that are defined by ordinary equations (as opposed to fixpoint > equations) from the structure of the category at hand (such as > composition, pairing, the functor "X v Y", etc). i think such class of corecursive functions would be too narrow: eg, it seems that only a small part of the elements of the final coalgebra (the "rationals") can be captured as corecursive constants, at least as long as your basic operations are finitary. while the class of recursive functions is countable, the class of corecursive functions should not be, if constants are to be included. > What's the exact definition of "guarded" in this context? in stream and list coalgebra, a fairly obvious semantic condition covers not only the usual syntactical guard conditions, but also the convergence criteria for power series solutions of, say, diff eqns. it's in my CMCS98 paper @article{PavlovicD:GIFC author = "Dusko Pavlovi\'c", title = "Guarded induction on final coalgebras", journal = "E. Notes in Theor. Comp. Sci.", pages = "143--160", year = "1998", volume = "11", url = "http://www.elsevier.nl/locate/entcs", } saying "categorically" which operations are guarded wrt an arbitrary functor is less straightforward... or at least less easy to justify. i worked on this, but never managed to get a really convincing formulation. (a clumsy one is on my web page.) -- dusko From rrosebru@mta.ca Wed Jan 19 20:40:03 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA15505 for categories-list; Wed, 19 Jan 2000 19:32:10 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Wed, 19 Jan 2000 19:30:03 -0400 (AST) From: Richard Wood To: categories Subject: categories: preprint: A Basic Distributive Law Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The article whose abstract follows is available from ftp://ftp.tac.mta.ca/pub/mathcs/papers/rosebrugh/bdl.{dvi,ps} Regards to all, F. Marmolejo, R. Rosebrugh, RJ Wood -------------------------------------------------------------- A Basic Distributive Law F. Marmolejo, R. Rosebrugh, RJ Wood We pursue distributive laws between monads, particularly in the context of KZ-doctrines, and show that a very basic distributive law has (constructively) completely distributive lattices for its algebras. Moreover, the resulting monad is shown to be also the double dualization monad (with respect to the subobject classifier) on ordered sets. From rrosebru@mta.ca Wed Jan 19 22:11:46 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id VAA08671 for categories-list; Wed, 19 Jan 2000 21:11:17 -0400 (AST) X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs Date: Wed, 19 Jan 2000 20:05:27 -0500 (EST) From: Michael Barr X-Sender: barr@triples.math.mcgill.ca To: "Stephen H. Schanuel" cc: categories@mta.ca, Stephen H Schanuel Subject: categories: Re: Reals a la Eudoxus (updated from re: Tate Reals) In-Reply-To: <000c01bf622e$0ddd7c60$80213018@buf.adelphia.net> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: I don't want to be disagreeable, but it seems clear to me that this construction gives Cauchy reals, not Dedekind reals and only the latter can be said to go back to Eudoxus. Indeed, given a nearly function f, with bound B on the near linearity, it is easy to see that |(fn/n) - (fm/m)| =< B(1/n + 1/m) so that the sequence fn/n is Cauchy. Michael From rrosebru@mta.ca Thu Jan 20 18:23:00 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA16803 for categories-list; Thu, 20 Jan 2000 15:09:24 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001201851.TAA19362@fennec.inria.fr> X-Mailer: exmh version 2.0.2 2/24/98 To: categories@mta.ca Subject: categories: Applied Semantics Summer School APPSEM'2000 Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Date: Thu, 20 Jan 2000 19:51:19 +0100 From: Simao Desousa Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id OAA11577 Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Dear Colleagues, I apologize if you receive multiple copies of this message and would be grateful if you could distribute the Summer School Call For Participation given below Best regards, S. Sousa ---------------------------------------------------------------------- C A L L F O R P A R T I C I P A T I O N ------------------------------------------ INTERNATIONAL SUMMER SCHOOL ON APPLIED SEMANTICS ---APPSEM'2000--- Caminha, Portugal, 9-15 September 2000 http://www-sop.inria.fr/oasis/Caminha00/index.html OBJECTIVE AND BACKGROUND Programming languages are the basic tools with which all applications of computers are built. It is important, therefore, that they should be well designed and well implemented. Achieving these goals requires both a good theoretical understanding of programming language designs, and practical skills in the development of high quality compilers. The summer school is addressed to postgraduate students, researchers and industrials who want to learn about recent developments in programming language research, both in semantic theory and in implementation. The programme will consist of introductory and advanced courses on the following themes: - description of existing programming language features; - design of new programming language features; - implementation and analysis of programming languages; - transformation and generation of programs; - verification of programs. LOCATION The summer school is located in Caminha, a picturesque village by the sea and on the Rio Minho, on the northern border between Portugal and Spain. PROGRAMME - Andrew Pitts, Cambridge University. Operational Semantics. - John Hughes, Chalmers University, Eugenio Moggi, Genova University, and Nick Benton, Microsoft Research. Monads and Effects. - Pierre-Louis Curien, CNRS and Paris 7 University. Games and Abstract Machines. - Thierry Coquand, Chalmers University, and Gilles Barthe, INRIA. Dependent Types in Programming. - Olivier Danvy, BRICS and Peter Dybjer, Chalmers University. Normalization and Partial Evaluation. - Cédric Fournet, Microsoft Research and Georges Gonthier, INRIA. Join Calculus: a model for distributed programming. - Xavier Leroy, INRIA, and Didier Rémy, INRIA. Objects, Classes and Modules in Objective CAML. - Martin Odersky, Ecole Polytechnique Federale de Lausanne. Functional Nets. - Abbas Edalat, Imperial College, and Achim Jung, Birmingham University. Exact Real Number Computation. REGISTRATION The registration fees covers proceedings, full boarding, refreshments, social events and a banquet: - early registration (before April 21st) * single room: 120 000 PTE * double room: 100 000 PTE - late registration * single room: 140 000 PTE * double room: 120 000 PTE There is no deadline for late registration but accommodation is not guaranteed if you applied after the 1st July 2000. See http://www-sop.inria.fr/oasis/Caminha00/registration.html for further information. GRANTS Limited funds will be available for grants. The deadline for application for a grant is April 1st. You will receive notification of acceptance/rejection by April 8th. To apply for a grant, see http://www-sop.inria.fr/oasis/Caminha00/grant.html. FURTHER INFORMATION For further information, please contact the organizing committee by email (appsem-school@di.uminho.pt). From rrosebru@mta.ca Thu Jan 20 18:32:08 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id RAA20261 for categories-list; Thu, 20 Jan 2000 17:01:04 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: rbf@dai.ed.ac.uk Date: Wed, 19 Jan 2000 20:30:36 GMT Message-Id: <18988.200001192030@magpie> To: categories@mta.ca Subject: categories: MSc in Informatics (AI, CS, CogSci) at Edinburgh Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Master of Science (MSc) degrees in the Division of Informatics at the University of Edinburgh The Division of Informatics offers three 1 year courses in different topics in Informatics: 1. MSc in Artificial Intelligence, whose primary focus is on development and understanding of intelligent computational processes for the benefit of both creating useful artifacts and helping better understand intelligence (human or otherwise). The course contains five themes: Foundations of AI, Intelligent Robotics, Knowledge-based Systems, Natural Language Processing, and Non-Symbolic AI. 2. MSc in Cognitive Science and Natural Language. This MSc is concerned with computational, formal and experimental approaches to understanding cognition and natural language. In Cognitive Science, the disciplines of formal linguistics, psychology, neuroscience and philosophy are brought together in different kinds of computational frameworks. This MSc is particularly concerned with how language is represented and processed. 3. The MSc in Computer Science contains three themes. The Advanced Computer Systems theme embraces the theory and practice of designing programmable systems. The Systems Level Integration theme teaches the principles underlying the design of integrated software and hardware systems in silicon. The Theoretical Computer Science theme introduces students to core areas of theoretical Computer Science and to the technologies through which theory-based tools are implemented. Applicants should specify which course(s) they are applying for and which themes are of interest in order of priority. From October to April students attend taught modules. During the period May - September inclusive, each student undertakes a major practical project, theoretical dissertation or piece of experimental research under the supervision of a member of academic staff. The projects can involve industrial collaboration and may be proposed by the student. Together, the three courses receive over 40 studentships from the UK government, which support about 1/2 of the students on the courses. In general, students should have a good BS/BSc degree (or equivalent) in an appropriate topic, plus other skills appropriate to the particular MSc course. More information can be found on the Division's MSc WWW page at: http://www.informatics.ed.ac.uk/prospectus/graduate/ For further information, contact: MSc Admissions Secretary Division of Informatics University of Edinburgh 5 Forrest Hill Edinburgh, EH1 2QL Scotland, UK Fax: +44-(131)-650-6899 Telephone: +44-(131)-650-3904 Email: msc-admissions@inf.ed.ac.uk **************** ALSO: PhD Positions Available **************** We also have a thriving PhD program. For more information, see: http://www.informatics.ed.ac.uk/prospectus/graduate/ From rrosebru@mta.ca Thu Jan 20 18:39:47 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id RAA20348 for categories-list; Thu, 20 Jan 2000 17:01:18 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: rbf@dai.ed.ac.uk Date: Wed, 19 Jan 2000 20:40:16 GMT Message-Id: <19193.200001192040@magpie> To: categories@mta.ca Subject: categories: PhD in Informatics (AI, CS, CogSci) at Edinburgh Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: PhD degrees in the Division of Informatics at the University of Edinburgh In 1998, the University of Edinburgh established a Division of Informatics, to study the structure, behaviour and interactions of both natural and artificial computational systems. The Division reflects the University's vision of Informatics as a fundamental area of study, critical for the future developments in science, engineering, and society. The Division was formed from the former Departments of Artificial Intelligence, Cognitive Science and Computer Science. The Division has positions for new research degree students pursing either an MSc(Research) (one year), an MPhil (two years) or a PhD (three years) through investigation of open problems in Informatics. The Division now contains about 70 academic staff, 60 contract researchers and 150 research students, grouped primarily into these research institutes: Artificial Intelligence Applications Institute Institute for Adaptive and Neural Computation Institute for Communicating and Collaborative Systems Institute for Computing Systems Architecture Institute of Perception, Action and Behaviour Institute for Representation and Reasoning Laboratory for Foundations of Computer Science which reflect the main research themes in the Division: adaptive computing artificial intelligence automated and mathematical reasoning cognitive science computational complexity computational learning theory computational linguistics computational musicology computational neuroscience computer-assisted formal reasoning computer architectures and networking computer communication and protocols computer graphics and virtual reality computer science computer vision database systems design and analysis of dependable systems diagramatic understanding formal program specification functional, logic and object-oriented programming genetic/evolutionary algorithms human-computer interaction intelligent tutoring systems knowledge representation and reasoning knowledge-based systems machine learning medical informatics mobile and assembly robotics modular and component-based systems natural language processing neural modelling neural networks neuroinformatics parallel, distributed and concurrent systems planning and activity management probabilistic graphical models program logics programming languages qualitative and fuzzy reasoning semantics of programming languages software engineering speech understanding and generation system level design and integration theory of computation type theory The UK Engineering and Physical Science Research Council has awarded the Division about 8 full studentships that can be used by UK and EC students. Overseas students may be eligible for ORS awards, that pay approximately half of the total costs. In general, students should have a good BS/BSc degree (or equivalent) in an appropriate topic, plus other skills appropriate to the particular research area. More information can be found on the Division's PhD WWW page at: http://www.informatics.ed.ac.uk/prospectus/graduate/ For application forms and further information, contact: PhD Admissions Secretary Division of Informatics University of Edinburgh James Clerk Maxwell Building King's Buildings Mayfield Road Edinburgh EH9 3JZ Email: phd-admissions@inf.ed.ac.uk Fax: +44 131 667 7209 Telephone: +44 131 650 5156 Please contact us if you'd like to come for a visit. **************** ALSO: MSc Positions Available **************** We also have three thriving taught MSc courses in Artificial Intelligence, Cognitive Science and Computer Science. For more information, see: http://www.informatics.ed.ac.uk/prospectus/graduate/ From rrosebru@mta.ca Thu Jan 20 19:00:07 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA07643 for categories-list; Thu, 20 Jan 2000 16:19:17 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f To: afp@cs.chalmers.se, bra-types@cs.chalmers.se, categories@mta.ca, ccl@dfki.uni-sb.de, clics@doc.ic.ac.uk, compass-wg@bettina.informatik.uni-Bremen.de, concurrency@cwi.nl, csp-list@cert.fr, eacsl@dimi.uniud.it, eapls@mailbase.ac.uk, fairouz@cee.hw.ac.uk, formal-methods@cs.uidaho.edu, isabelle-users@cl.cam.ac.uk, libkin@research.bell-labs.com, lics-request@research.bell-labs.com, logic@CS.Cornell.EDU, rewriting@loria.fr, theorem-provers@mc.lcs.mit.edu, types@cis.upenn.edu Subject: categories: Position announcement Message-Id: From: Fairouz Kamareddine Date: Thu, 20 Jan 2000 18:46:11 +0000 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: RESEARCH POSTS AVAILABLE LOGICS, TYPE THEORY, TERM REWRITING FOUNDATIONS OF PLs and TPs Heriot-Watt University, Edinburgh, Scotland ------------------------------------- Research posts are available at the department of Computing and Electrical Engeneering at Heriot-Watt University, Edinburgh Scotland within the ULTRA group (see http://www.cee.hw.ac.uk/ultra/). We are targeting researchers in the foundations, design and implementation of programming languages and of Theorem Proving. Competence in at least one of Type Theory, Lambda Calculus and Term Rewriting is essential. The posts are initially for a period of six months but may be renewable depending on performance, results and funding. The department of Computing and Electrical at Heriot-Watt is a very lively, active and friendly place with a supportive spirit. The department is expanding fast and is committed to excellence and is investing a lot in the future. Heriot-Watt is located in beautiful parklands on the outskirsts of Edinburgh, the capital of Scotland and a beautiful and historic city. If you are interested, email us your Curriculum Vitae and the names and email addresses of 3 referees. CVs and/or questions should be sent to: Fairouz Kamareddine (fairouz@cee.hw.ac.uk) or Joe Wells (jbw@cee.hw.ac.uk). From rrosebru@mta.ca Fri Jan 21 11:03:43 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA32103 for categories-list; Fri, 21 Jan 2000 09:42:29 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <000b01bf63b8$33d088a0$80213018@buf.adelphia.net> From: "Stephen H. Schanuel" To: Subject: categories: Eudoxus and the real numbers Date: Thu, 20 Jan 2000 21:35:34 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2919.6600 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: About 'disagreeable': As far as I can see, Mike Barr and I don't disagree. I had trouble figuring out how to post something on the catnet, so when my original note didn't appear, I added a couple of details and reposted; I think that the second one was a bit clearer about what I was crediting to Eudoxus, namely just the idea that cutting the measuring stick into n equal parts to improve accuracy is unnecessary, and can be replaced by multiplying the stick one wants to measure by n. (If I'm wrong in crediting that to Eudoxus, somebody please enlighten me.) Now isn't it reasonable to say that this simple observation ought to suggest that R can be constructed without first constructing Q? (The only surprise is that it doesn't require Z as ring, but only as unordered abelian group.) Whether Eudoxus was constructing the Cauchy reals or the Dedekind reals (or the positive half of those) or 'constructing' anything at all--which I don't think he was--is irrelevant to the point above, I think. Of course I agree with Mike that the construction which I based on E's observation gives the Cauchy reals, as I believe Mike pointed out many years ago in Montreal when I neglected to make the distinction in a talk I gave there. He was and is right to make this 'modern' Cauchy versus Dedekind distinction, and if someone can show me that it isn't modern, that would be even more interesting! From rrosebru@mta.ca Fri Jan 21 11:06:17 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA32052 for categories-list; Fri, 21 Jan 2000 09:40:37 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f To: categories@mta.ca, types@cis.upenn.edu From: Lars Birkedal Subject: categories: Announcement: PhD-thesis Date: Thu, 20 Jan 2000 16:32:16 -0500 Message-ID: <23680.948403936@smoked.fox.cs.cmu.edu> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: I would like to announce that my PhD-thesis, titled Developing Theories of Types and Computability via Realizability and written under the guidance of Prof. Dana S. Scott at Carnegie Mellon University is now available at http://www.cs.cmu.edu/~birkedal/papers.html (as are a couple of papers related to the thesis). The abstract follows below. Best regards, Lars Birkedal ---------------------------------------------------------------------- Abstract: We investigate the development of theories of types and computability via realizability. In the first part of the thesis, we suggest a general notion of realizability, based on weakly closed partial cartesian categories, which generalizes the usual notion of realizability over a partial combinatory algebra. We show how to construct categories of so-called assemblies and modest sets over any weakly closed partial cartesian category and that these categories of assemblies and modest sets model dependent predicate logic, that is, first-order logic over dependent type theory. We further characterize when a weakly closed partial cartesian category gives rise to a topos. Scott's category of equilogical spaces arises as a special case of our notion of realizability, namely as modest sets over the category of algebraic lattices. Thus, as a consequence, we conclude that the category of equilogical spaces models dependent predicate logic; we include a concrete description of this model. In the second part of the thesis, we study a notion of relative computability, which allows one to consider computable operations operating on not necessarily computable data. Given a partial combinatory algebra A, which we think of as continuous realizers, with a subalgebra A#, which we think of as computable realizers, there results a realizability topos RT(A,A#), which one intuitively can think of as having ``continous objects and computable morphisms''. We study the relationship between this topos and the standard realizability toposes RT(A) and RT(A#) over A and A#. In particular, we show that there is a localic local map of toposes from RT(A,A#) to RT(A#). To obtain a better understanding of the relationship between the internal logics of RT(A,A#) and RT(A#), we then provide a complete axiomatization of arbitrary local maps of toposes, a new result in topos theory. Based on this axiomatization we investigate the relationship between the internal logics of two toposes connected via a local map. Moreover, we suggest a modal logic for local maps. Returning to the realizability models we show in particular that the modal logic for local maps in the case of RT(A,A#) and RT(A#) can be seen as a _modal logic for computability_. Moreover, we characterize some interesting subcategories of RT(A,A#) (in much the same way as assemblies and modest sets are characterized in standard realizability toposes) and show the validity of some logical principles in RT(A,A#). From rrosebru@mta.ca Fri Jan 21 15:35:04 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id OAA28413 for categories-list; Fri, 21 Jan 2000 14:12:42 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <38884900.195DC903@di.fc.ul.pt> Date: Fri, 21 Jan 2000 11:54:40 +0000 From: Nuno Barreiro X-Mailer: Mozilla 4.6 [en] (X11; I; Linux 2.0.36 i686) X-Accept-Language: en MIME-Version: 1.0 To: categories@mta.ca Subject: categories: The LINEAR International Summer School Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The LINEAR International Summer School (Linear Logic and Applications) August 30 to September 7, 2000 Hotel Terra Nostra, S.Miguel, Azores, Portugal The Linear TMR research network (http://iml.univ-mrs.fr/LINEAR) is proud to announce its first International Summer School on Linear Logic and Applications. The school lasts one week and comprises both lectures and thematic sessions directed to young computer scientists and mathematicians interested in the field of formal logic and its applications. The lectures are in the tradition of summer schools and cover one topic, from basic material to more advanced issues. The topics and lecturers are the following: Samson Abramsky --- Game Semantics Jean-Yves Girard -- Linear Logic and Ludics Stefano Guerrini -- Proof-Nets and Lambda-Calculus Yves Lafont ------- Phase Semantics and Decision Problems Phil Scott -------- Category Theory and Concrete Models The thematic sessions will cover state-of-the-art research in Linear Logic. Each session has an organiser responsible for inviting speakers who will talk about their work. The themes and organisers are the following: Andrea Asperti ---- Applications Vincent Danos ----- Proof Theory Thomas Ehrhard ---- Semantics Glynn Winskel ----- Concurrency The school will be held in the island of S.Miguel, Azores, amid luxurious vegetation and hot water springs. The entrance to the mythic kingdom of the Atlantis is believed to be located near Hotel Terra Nostra, some say at the bottom of its famous red and hot water swimming pool... Mark the dates on your agenda now. Up-to-date information, including the application form, is being made available at http://linear.di.fc.ul.pt Don't forget to check it! From rrosebru@mta.ca Sat Jan 22 12:36:31 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA23716 for categories-list; Sat, 22 Jan 2000 10:34:39 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sat, 22 Jan 2000 08:54:30 -0500 (EST) From: Peter Freyd Message-Id: <200001221354.IAA11647@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: Dedekind v Cantor Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Folklore says that Book V of Euclid's Elements is the best extant approximation to Eudoxus. The Joyce translation: Euclid's Elements Book V Definition 5 Magnitudes are said to be in the same ratio, the first to the second and the third to the fourth, when, if any equimultiples whatever are taken of the first and third, and any equimultiples whatever of the second and fourth, the former equimultiples alike exceed, are alike equal to, or alike fall short of, the latter equimultiples respectively taken in corresponding order. (http://aleph0.clarku.edu/~djoyce/java/elements/bookV/bookV.html#defs) It looks more Dedekind than Cantor to me (why do people think that Cauchy had anything to do with this?). But Steve is right when he says that the rational numbers don't appear: an incommensurable ratio is described as a partitioning of pairs of integers. According to Neugebauer the philosophical Greeks avoided the rationals: they allowed _ratios_ named by pairs of integers, and they effectively knew how to multiply ratios; but they considered the addition of ratios as something allowed only by those entirely unphilosophical calculators to be found in marketplaces. From rrosebru@mta.ca Mon Jan 24 12:39:52 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id KAA08082 for categories-list; Mon, 24 Jan 2000 10:16:01 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Sun, 23 Jan 2000 14:55:25 -0800 (PST) Message-Id: <200001232255.OAA20545@Steam.Stanford.EDU> From: Carolyn Talcott To: categories@mta.ca Subject: categories: FMOODS'2000 cfp Reply-to: clt@cs.stanford.edu Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: The usual apologies for multiple copies ============================================================================== Call for Papers FMOODS 2000 IFIP TC6/WG6.1 Fourth International Conference on Formal Methods for Open Object-Based Distributed Systems Stanford University , Stanford, California, USA September 6-8, 2000 ------------------------------------------------------------------------ Electronic Information * The conference home page is found at http://www.ics.uci.edu/~fmds2000 * Conference-related email should be addressed to fmoods2000@cs.stanford.edu * Information on the FMOODS series of conferences can be found at http://www.cs.ukc.ac.uk/research/netdist/fmoods ------------------------------------------------------------------------ Important Dates 1st March 2000 Submission deadline 30th April 2000Notification of acceptance 23rd May 2000 Camera ready copy for participants proceedings due ------------------------------------------------------------------------ Co-located with SPIN'2000, 7th International SPIN Workshop on Model Checking of Software, to be held at Stanford the previous week August 30-31, September 1. See: http://ase.arc.nasa.gov/spin2000 ------------------------------------------------------------------------ Objectives Object-based Distributed Computing is being established as the most pertinent basis for the support of large, heterogeneous computing and telecommunications systems. Indeed, several important international organisations, such as ITU, ISO, OMG, TINA-C, etc. are defining similar distributed object-based frameworks as a foundation for open distributed computing. The advent of Open Object-based Distributed Systems - OODS - brings new challenges and opportunities for the use and development of formal methods. New architectures and system models are emerging (e.g., the enterprise, information, computational and engineering viewpoints of the ITU-T/ISO/IEC ODP Reference Model) which require formal notational support. Usual design issues such as specification, verification, refinement, and testing need to take into account new dimensions introduced by distribution and openness, such as quality of service and dependability constraints, dynamic binding and reconfiguration, consistency between multiple models and viewpoints, etc. OODS is a challenging research context and a source of motivation for semantical models of object-based systems and notations, for the evolution of standardised formal description techniques, for the application and assessment of logic based approaches, for better understanding and information modeling of business requirements, and for the further development and use of Object Oriented methodologies and tools. The objective of FMOODS is to provide an integrated forum for the presentation of research in several related fields, and the exchange of ideas and experiences in the topics concerned with the formal methods support for Open Object-based Distributed Systems. Topics of interest include but are not limited to: * formal models for object-based distributed computing * semantics of object-based distributed systems and programming languages * formal techniques in object-based and object-oriented specification, analysis and design * refinement and transformation of specifications * types, service types and subtyping * interoperability and composability of distributed services * object-based coordination languages * object-based mobile languages * efficient analysis techniques of specifications * multiple viewpoint modelling and consistency between different models * formal techniques in distributed systems verification and testing * specification, verification and testing of quality of service constraints * formal methods and object life cycle * beyond IDL: semantics based specification patterns * formal models for measuring the quality of object-oriented requirement or design specifications * formal aspects of distributed real-time multimedia systems * applications to telecommunications and related areas ------------------------------------------------------------------------ Invited Speakers: Jose Meseguer, SRI International and others to be announced ------------------------------------------------------------------------ Conference Organizers Carolyn Talcott(Chair) Scott Smith(PC Chair) Tel: + 650 723-0936 Tel: + 410 516-5299 Fax: + 650 725-7411 Fax: + 410 516-6134 Stanford University The Johns Hopkins University Stanford, CA, USA Balimore, MD, USA clt@cs.stanford.edu scott@cs.jhu.edu Nalini Venkatasubramanian Sriram Sankar Tel: + 949 824-5898 Tel: + 510 796-0915 Fax: + 949 824-4056 Fax:+ 510 796-0916 University of California at Irvine Metamata Inc. Irvine, CA, USA Fremont, CA, USA nalini@ics.uci.edu sriram.sankar@metamata.com Program Committee * Gul Agha (U. of Illinois, USA) * Patrick Bellot (ENST, Paris, France) * Lynne Blair (U. Lancaster, UK) * Howard Bowman (UKC, Kent, UK) * Paolo Ciancarini (U. Bologna, Italy) * John Derrick (UKC, Kent, UK) * Michel Diaz (LAAS-CNRS, Toulouse, France) * Alessandro Fantechi (U. Firenze, Italy) * Kathleen Fisher (ATT Research Labs, USA) * Kokichi Futatsugi (Jaist, Ishikawa, Japan) * Joseph Goguen (UC San Diego, USA) * Roberto Gorrieri (U. Bologna, Italy) * Guy Leduc (U. of Liege, Belgium) * Luigi Logrippo (U of Ottawa, Canada) * David Luckham (Stanford University, USA) * Jan de Meer (GMD Fokus, Berlin, Germany) * Elie Najm (ENST, Paris, France) * Dusko Pavlovic (Kestrel Institute, USA) * Omar Rafiq (U. of Pau, France) * Arend Rensink (U. Twente, Netherlands) * Sriram Sankar (Metamata Inc., USA) * Gerd Schuermann (GMD Fokus, Berlin, Germany) * Scott Smith (Johns Hopkins University, USA) * Jean-Bernard Stefani (FT/CNET, Issy-les-Moulineaux, France) * Carolyn Talcott (Stanford University, USA) * Nalini Venkatasubramanian (UC Irvine, USA) Sponsors - IFIP ------------------------------------------------------------------------ Evaluation and Publication of Submitted Papers Submitted manuscripts will be evaluated and selected for presentation in the conference. The proceedings of FMOODS '00 will be published by Kluwer, the publishers of IFIP events. The proceedings will be made available at the conference. Instructions to the Authors Authors are invited to submit full original research papers, up to 16 pages (including bibliography), 12 point, single spaced, including an informative abstract, names and affiliations of all authors, and a list of keywords facilitating the assignment of papers to referees. Submission Paper submissions will be electronic via the web. Papers must be submitted as postscript documents that are interpretable by Ghostscript. Details on the submission process are to be found at http://www.ics.uci.edu/~fmds2000. The package for electronic submission of papers will be available approximately one month before the submission deadline. ------------------------------------------------------------------------ From rrosebru@mta.ca Mon Jan 24 18:03:33 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA06018 for categories-list; Mon, 24 Jan 2000 16:59:03 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 24 Jan 2000 20:14:36 +0100 (MET) Message-Id: <200001241914.UAA23504@agaric.ens.fr> From: "Martin H. Escardo" To: categories@mta.ca Subject: categories: Freyd's couniversal characterization of [0,1] Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: It would be interesting to test Freyd's couniversal characterization of the unit interval in many other categories. Here I test it in Top, the category of topological spaces and continuous maps, and various full subcategories, where one would hope to get the unit interval with the Euclidean topology. ---------------------------------------------------------------------- Summary of the outcome of some tests: (1) In Top, the final coalgebra for Freyd's functor exists. Its underlying object, however, is an indiscrete space (unsurprisingly). (2) In the category of T0 spaces, it doesn't exist. (3) In the category of normal spaces it does exist, and, as one would hope, its underlying object is indeed the unit interval with the Euclidean topology. See remark below for weakening normality in (3) as much as possible. ---------------------------------------------------------------------- Arguments follow. We work with the category BiTop of bipointed topological spaces, whose objects are topological spaces with two distinct distinguished points and whose morphisms are continuous maps that preserve the two distinguished points. Given a bipointed topological space x0,x1:1->X, one constructs a bipointed topological space FX as in the diagram below, where the square is a pushout. inr x1 FX <--------- X <---------- 1 ^ ^ | | inl | | x0 | | X <---------- 1 ^ x1 | x0 | | 1. Thus, FX is the quotient of the coproduct of two copies of X that identifies two points (x1 of the first copy with x0 of the second). It is clear how F extends to morphisms producing a functor BiTop->BiTop. (1)----------------------------------------------------------------- Is there a final coalgebra d:I->FI in BiTop? In BiSet, Freyd argued, one can take I=[0,1] with distinguished points 0 and 1 and structure map d defined by d(x) = inl(2x) if x<=1/2 inr(2x-1) if x>=1/2 Notice that for x=1/2 one gets inl(1)=inr(0), as one should. [[Incidentally, see M.H. Escardo and Th. Streicher. "Induction and recursion on the partial real line with applications to Real PCF", TCS 210(1999) 121-157. There, essentially the same definition gives a final coalgebra whose inverse is an initial algebra, but the underlying category is that of continuous Scott domains.]] By general trivial reasons, the same construction works in BiTop if one endows X with the indiscrete topology: Uniqueness and existence of a set-theoretic map follow by Freyd's argument, and any map with values in an indiscrete space is continuous. (2)------------------------------------------------------------------ Now consider the category of T0 spaces. For the sake of contradiction, assume that there is a final coalgebra d:X->FX where X has distinguished points x0 and x1. Let S be the space with two points 0 and 1 such that {1} is open but {0} is not (Sierpinski space). We use the facts that 0<=1 in the specialization order (every neighbourhood of 0 is also a neighbourhood of 1) and that continuous maps preserve the specialization order. Let A be S with distinguished points 0 and 1 (in this order). Then FA has points 0,1/2,1 with distinguished points 0 and 1. So there is a unique morphism A->FA. By the alleged finality of d:X->FX there is a unique homomorphism h:A->X. Since h(0)=x_0 and h(1)=x_1, by continuity of h we conclude that x0<=x1 in the specialization order. By swapping the order of the distinguished points of S, we also conclude that x1<=x0. Thus, x0 and x1 have the same neighbourhoods. By the T0 property, they are equal, which contradicts the definition of a bipointed topological space. (3)------------------------------------------------------------------ Now consider the category of normal spaces. We use Urysohn's Lemma and Banach's Fixed Point Theorem to show that Freyd's construction works here if one endows I=[0,1] with the Euclidean topology. First, d:I->FI as defined by above is clearly a homeomorphism with inverse c:FI->I given by c(inl(x))=x/2 c(inr(x))=(x+1)/2. (NB. "d" stands for "destructor" and "c" for "constructor".) Thus, if D:X->FX is a coalgebra, to say that h:X->I is a coalgebra homomorphism is the same as saying that h = c o Fh o D We thus consider the obvious functional H:C(X,I)->C(X,I) where C(X,I) is the set of continuous maps from X to I, namely H(h) = c o Fh o D. (I know, the domain and codomain of H should consist of BiTop morphisms rather than continuous maps; this (co)restriction will be performed very shortly). We endow C(X,I) with the sup-metric, which is well-defined as I is bounded. It is well-known that this is a complete metric space with limits of Cauchy sequences computed pointwise. We consider the subspace B(X,I) of BiTop morphisms. First, it is non-empty by Urysohn's Lemma. And this is where the assumption of normality is used (albeit not in its full strength). Second, it is a complete subspace, as limits are computed pointwise. Third, H trivially (co)restricts to a functional H:B(X,I)->B(X,I). Thus, in order to obtain the desired conclusion, all we have to do is to show that H:B(X,I)->B(X,I) is contractive. For every x in X, we have that D(x) is of one of the forms inl(y) or inr(z), for which we respectively get that, for any h in B(X,I), H(h)(x)= c o Fh o inl(y)=h(y)/2 or H(h)(x)= c o Fh o inr(z)=(h(z)+1)/2. Hence in each case we respectively get that |H(h)(x)-H(g)(x)|=|h(y)/2-g(y)/2| =|h(y)-g(y)|/2 or |H(h)(x)-H(g)(x)|=|(h(z)+1)/2-(g(z)+1)/2|=|h(z)-g(z)|/2 By definition of the sup-metric, the distance from H(h) to H(g) is the sup of |H(h)(x)-H(g)(x)| over all x. By the above argument this is smaller than the sup of |h(t)-g(t)|/2 over all t (because the sup of a larger set is bigger), which is half the distance from h to g. Therefore H is contractive. Q.E.D Remark --------------------------------------------------------------- Normality in (3) can be generalized to the requirement that for any two distinct points there is a function into the unit interval that maps one of the points to 0 and the other to 1 (weak normality). This is stronger than Hausdorffness and weaker than normality by Urysohn's Lemma. But this definition uses the very object that we want to "construct". Does anyone know a characterization of weak normality that doesn't refer to real numbers? It is easy to see that the assumption that the unit interval with the Freyd's structure is final in BiC for some subcategory C of Top implies that all spaces of C are weakly normal. Thus, the largest full subcategory of Top for which the Euclidean unit interval with Freyd's structure map is a final coalgebra consists precisely of the weakly normal spaces. ---------------------------------------------------------------------- Question: What does one get in full subcategories of locales and of equilogical spaces? ---------------------------------------------------------------------- mailto:mhe@dcs.st-and.ac.uk http://www.dcs.st-and.ac.uk/~mhe/ ---------------------------------------------------------------------- From rrosebru@mta.ca Mon Jan 24 18:24:54 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA03950 for categories-list; Mon, 24 Jan 2000 16:56:53 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Sender: ageron@mail.math.unicaen.fr Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" To: categories@mta.ca From: Pierre Ageron Subject: categories: SEMINAIRE ITINERANT SUR LES CATEGORIES Date: Mon, 24 Jan 2000 16:16:33 +0100 (CET) Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id LAA28352 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: SEMINAIRE ITINERANT SUR LES CATEGORIES SAMEDI 29 JANVIER 2000 à l'Université de Caen. PROGRAMME (susceptible de modifications) 9.15 Dominique Bourn (Calais) "Sous-objets normaux dans les catégories protomodulaires" 10.15 Christophe Tabacznyj (CEA Saclay) "Interprétation de programmes dans un topos" 11.00 Enrico Vitale (Louvain-la-Neuve) "Complétion de catégories et quasi-variétés d'algèbres" 13.30 Albert Burroni (Paris 7) "Opérades et T-catégories" 14.30 Christian Lair (Paris 7) "Existence d'objets terminaux dans les catégories de modèles et ré-esquissabilite" 15.30 Andrée Charles-Ehresmann (Amiens) "Colimites locales et applications" PIERRE AGERON ------------------------------------------------------- ATTENTION. Je suis en congé pour recherches (dit "congé sabbatique") pour six mois à compter du 1er février 2000. Pendant cette période, je ne passerai dans mon bureau qu'une fois par semaine, le mardi après-midi. Si c'est urgent, il est donc préférable de me téléphoner à mon domicile plutôt que de m'envoyer un message électronique. ------------------------------------------------------- 1) coordonnées bureau adresse: Département de mathématiques, Université de Caen, 14032 Caen Cedex (mon bureau se trouve désormais sur le Campus 2, bât. Sciences 3, pièce 322) téléphone : 02 31 56 74 67 télécopie : 02 31 56 73 20 adresse électronique : ageron@math.unicaen.fr page personnelle : http://matin.math.unicaen.fr/~ageron/ 2) coordonnées domicile adresse : 28 rue de Formigny 14000 Caen téléphone : 02 31 84 39 67 From rrosebru@mta.ca Mon Jan 24 19:12:35 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id QAA05832 for categories-list; Mon, 24 Jan 2000 16:58:04 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 24 Jan 2000 10:26:41 -0500 (EST) X-Sender: marquisj@poste.umontreal.ca Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: categories@mta.ca From: Jean-Pierre Marquis Subject: categories: re: Dedekind v Cantor Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: >It looks more Dedekind than Cantor to me (why do people think that >Cauchy had anything to do with this?). In his "Analyse algebrique" (1821), Cauchy gives the first (still informal) definition of a limit and says (without proof), in order to illustrate the concept, that an irrational number is the limit of the various rational sequences approximating it. He also gives various criteria for convergence. Thus, although Cauchy certainly does not give a rigorous and formal construction of the reels, people ascribe to him the basic idea. But then, perhaps Bolzano, Weierstrass, Meray and Heine should also be mentioned, no? >But Steve is right when he says >that the rational numbers don't appear: an incommensurable ratio is >described as a partitioning of pairs of integers. A relevant reference here is: Stein, H., 1990, 'Eudoxus and Dedekind: On the ancient greek theory of ratios and its relation to modern mathematics', Synthese, 84, 163-211. Jean-Pierre Marquis From rrosebru@mta.ca Mon Jan 24 21:10:08 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id TAA08475 for categories-list; Mon, 24 Jan 2000 19:10:20 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <388C7A2D.6F2666B6@cs.nmsu.edu> Date: Mon, 24 Jan 2000 09:13:33 -0700 From: Enrico Organization: Laboratory for Logic & Databases X-Mailer: Mozilla 4.61 [en] (X11; U; Linux 2.0.36 i686) X-Accept-Language: en MIME-Version: 1.0 To: afp@cs.chalmers.se, bra-types@cs.chalmers.se, categories@mta.ca, ccl@dfki.de, clics@doc.ic.ac.uk, compass-wg@bettina.informatik.uni-bremen.de, concurrency@cwi.nl, csp-list@cert.fr, eacsl@dimi.uniud.it, eapls@mailbase.ac.uk, fairouz@cee.hw.ac.uk, formal-methods@cs.uidaho.edu, isabelle-users@cl.cam.ac.uk, libkin@research.bell-labs.com, lics-request@research.bell-labs.com, logic@CS.Cornell.EDU, rewriting@loria.fr, theorem-provers@mc.lcs.mit.edu, types@cis.upenn.edu Subject: categories: Job Announcement: New Mexico State University Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: New Mexico State University Department of Computer Science The New Mexico State University Department of Computer Science invites applications for one or two tenure-track assistant/associate professor position(s) in computer science beginning academic year 2000-2001. Strong commitment to both research and teaching required. Applications from women and members of minority groups invited. Qualifications include a Ph.D. in Computer Science or closely related discipline (in hand by date of hire) and evidence of strength in teaching and research. The Department has 12 tenure-track faculty positions, and offers B.S., M.S., and Ph.D. degrees. The Department collaborates with the Computing Research Laboratory (CRL), an independent research center at NMSU. Departmental facilities include a network of some 60 Sparc workstations, a 14-processor Sun Sparc, a 32-node Beowulf, and several other multiprocessors. The Department recently received $1.5m grant from NSF to upgrade its infrastructure. Arrange for vita, short research description, and at least three reference letters to be sent by postal mail directly to: Faculty Recruiting Committee, Department of Computer Science, NMSU MSC CS, PO Box 30001, Las Cruces, NM 88003-8001. Application review will begin January 31, 2000. NMSU is an EEO/AA employer. From rrosebru@mta.ca Tue Jan 25 16:45:46 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA30872 for categories-list; Tue, 25 Jan 2000 15:32:46 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 25 Jan 2000 15:11:09 -0400 (AST) From: TAC To: categories@mta.ca Subject: categories: TAC Contents: Volume 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Here is the table of contents and subscription information for Volume 5 of Theory and Applications of Categories. The Editors invite high quality submissions. The full table of contents is at www.tac.mta.ca/tac/ THEORY AND APPLICATIONS OF CATEGORIES ISSN 1201-561X Volume 5 - 1999 1. A note on discrete Conduche fibrations Peter Johnstone, 1-11 2. A tensor product for Gray-categories Sjoerd Crans, 12-69 3. A note on the exact completion of a regular category, and its infinitary generalizations Stephen Lack, 70-80 4. A useful category for mixed Abelian groups Grigore Calugareanu, 81-90 5. Distributive laws for pseudomonads Francisco Marmolejo, 91-147 6. Convergence in exponentiable spaces Claudio Pisani, 148-162 7. Double categories, 2-categories, thin structures and connections Ronald Brown and Ghafar Mosa, 163-175 8. Chu-spaces, a group algebra and induced representations Eva Schlaepfer, 176-201 9. When projective does not imply flat, and other homological anomalies L. Gaunce Lewis, Jr., 202-250 10. Aspects of fractional exponent functors Anders Kock and Gonzalo Reyes, 251-265 11. Generalized congruences -- Epimorphisms in Cat M.Bednarczyk, A.Borzyszkowski, W.Pawlowski, 266-280 12. Localizations of Maltsev varieties Marino Gran and Enrico Maria Vitale, 281-291 SUBSCRIPTION/ACCESS TO ARTICLES Subscribers to the journal receive abstracts of accepted papers by electronic mail. Compiled TeX (.dvi) and Postscript files of the full articles are available by WWW/ftp. To subscribe, send a request to tac@mta.ca , including your name and a postal address. The journal is free to individuals. University Departments, Libraries, and other institutional subscribers are invited to consult with the Managing Editor about subscription and archiving. Authors retain copyright to articles appearing in the Journal. The Journal is copyright by its Editorial Board. For further information, contact the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca . From rrosebru@mta.ca Tue Jan 25 16:50:21 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA30326 for categories-list; Tue, 25 Jan 2000 15:32:08 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-ID: <20000125182605.15344.qmail@web119.yahoomail.com> Date: Tue, 25 Jan 2000 10:26:05 -0800 (PST) From: Nikita Danilov Subject: categories: Quote To: categories@mta.ca MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Hello All, I hope you will find the following quote amusing: Something great and hard to describe a topos seems to be, for it is a matter and a form simultaneously. Aristotle. Physics (4) 212a Be warned however that this is the translation to English of the Russian translation of the Greek original. English translation by R. P. Hardie and R. K. Gaye uses ``place'' in stead of ``topos''. Nikita. From rrosebru@mta.ca Tue Jan 25 18:09:35 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA05188 for categories-list; Tue, 25 Jan 2000 15:55:53 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Tue, 25 Jan 2000 15:48:19 -0400 (AST) From: TAC To: categories@mta.ca Subject: categories: TAC: Author information Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: For reference, the Information for Authors page of Theory and Applications of categories follows. It has been updated with assistance from Michael Barr. The TAC style (tac.sty) and class (tac.cls) files have also been updated, so please replace any copies you may have. AUTHOR INFORMATION Theory and Applications of Categories (TAC) is an all-electronic journal which uses the TeX typesetting system to define its contents and the Internet to disseminate them. Authors are invited to submit articles to any member of the Editorial Board. While any standard flavour of TeX (i.e. plain, LaTeX, AMS-(La)Tex) may be submitted, the most important request to an author of a TAC paper is to use one or another version of LaTeX. This encourages the logical formatting that is described below. Before submitting an article please read about the Format for submission . All papers are refereed and acceptance of an article by an Editor indicates that the high standards of the journal have been met. Articles may be submitted to only one member of the Board. The final accepted version of a paper is the form that will be in the archive; the author will not be able to make any changes, except: errata and additions can be attached to the end and, where appropriate, footnote(s) may be added to the main text calling attention to these addendums; references which mention pre-publication versions may be updated to final bibliographic form. Accepted papers will be archived electronically in .dvi and Postscript format by the journal. In addition, there are several complete mirrors of the journal's contents on the Internet. A printed paper copy of each article in the journal is archived in the Mount Allison University Library. Authors retain ownership of copyright to their work, subject to appropriate use of the work by the journal. For details consult the Copyright Agreement, to which authors must agree before an accepted paper is published. FORMAT FOR SUBMISSION: SOURCE FILES TeX source files of articles may be submitted by email to any member of the Editorial Board. Editors may also provide facilities for receiving articles by file transfer. Editors will not correct errors in TeX source. It is the author's responsibility to provide a compilable source file. The source file for an article must begin with a comment which includes the following information: the flavour of TeX used, the number of pages, any diagram macro package used, any non-standard fonts, the implementation of TeX used in preparation of the article. An example might be % LaTeX 2.09 document, 12 pp, XY-pic ver 3.1, emTeX version 3.1 An article is normally submitted as a single source file. All macros must be included with the source file and are the responsibility of the author. Macros should be placed at the beginning of the file. It is also helpful if any macro that is not actually used is deleted from the source file. The only exception to inclusion of macros is diagram macro packages. The currently acceptable diagram macro packages are those authored by Barr, Borceux, Rose (XY-Pic) and Taylor. The author is responsible to ensure that the current version of a macro package has been used. Articles must include an Abstract, in English of not more than 200 words. AMS 2000 Subject Classification must also be also be included. SOURCE FILE STYLE As indicated above LaTeX is the preferred format. Using LaTeX will facilitate consideration of an article, but papers in other standard TeX flavors will be considered. A style file is available from the journal. Using the style file during preparation of articles will greatly reduce the acceptance to publication delay. Whether or not the journal's style is used, the most important advice for an author of TAC (or any electronic journal or even any journal that accepts TeXscripts) is to use logical, rather than physical formatting. That is, instead of beginning a section by saying \medskip \noindent{\bf 4.3 The main theorem.} just say \section{The main theorem}\label{mainth} (The \label will be explained below.) Instead of saying \smallskip \noindent{\sc Theorem A}{\it ...} say \begin{theorem}\label{thmA} ... \end{theorem} (shorter forms as will be explained later). You should probably NEVER put explicit skips and kerns into your paper. Suppose, for example, you want to go on to a new topic and want to leave a little space. The preferable way is to say \subsubsection*{} which will have exactly that effect. But in fact, it is probably always appropriate to start a new subsection in such a case. Except in very long papers, we discourage the use of three indexing levels. The point is to use symbolic formatting and let the journals put in their own style. All versions of LaTeX provide definitions for \section, \subsection, and \subsubsection. It even goes further, but these should be enough for nearly all papers. They do not provide definitions for \begin{theorem} and the like. But the TAC style files provide a \newtheorem macro that is used as follows. Place at the beginning of your paper, the following: \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} ... (whatever is needed) The first parameter is what you will call it in your TeXscript and the second what it will be called in your paper. So you can just as well say \newtheorem{thm}{Theorem} ... and then you can enclose your theorems in \begin{thm}...\end{thm} or even \thm...\endthm. Beware that you lose certain error checking with the latter form. AVOIDABLE ERRORS There are two mistakes made by many users of TeX that appear in print over and over and are easy to avoid. The first is to have multicharacter identifiers slanted (like math symbols), rather than in upright type. This refers to names like sin, cos,... but also Hom, Tor, Id, ker, Im, .... The TAC style files provide macros that can automate this. If you put in your file \mathrmdef{Hom} this will create a macro \Hom that will put upright Hom into your text. If you use that instead of just Hom, the results will look much better. Using just Hom in math mode will result in an italic font and ugly spacing that is more appropriate to a ternary product. TAC also supplies \mathbfdef (for bold), and \mathopdef (for upright characters that have a bit of extra space to the right, so that, say, \sin x will produce the sin, a small space and then an italic x, just as in the trig books). The second error is to use <...> for angle brackets. You have no idea how bad this will look. The < and > produce the wrong shape for angle brackets, but mainly they produce the wrong spacing and the results can be ludicrous, especially if an = follows > or precedes <. The official way to do this is to say \langle and \rangle. Many papers in TAC use these angle brackets extensively and make little or no use of the inequality signs. If this is your case, we recommend the following. At the top of your paper, put: \mathcode`\<="4268 %left delimiter \mathcode`\>="5269 %right delimiter \mathchardef\gt="313E %relation \mathchardef\lt="313C %relation The effect of the first two lines is to make < and > into \langle and \rangle, respectively, so that you can use them freely. The third and fourth lines allow you to use \lt and \gt for the inequality signs. This is not done in the TAC styles because an author has the right to use < and > for the inequalites if desired. Fonts Authors should note that the base font size is 12 point. Avoid use of elements which depend on another base font size. This is another reason to avoid absolute moves such as `\vskip 10 pt'. Remember that the journal's pagination will differ from yours. As a general rule less, but more logical, formatting is better. Authors are STRONGLY encouraged to use only fonts from the standard TeX distribution (cmr etc.), AMS symbol fonts (msym...) or the XY-pic fonts. They should be aware that use of non-standard fonts can interfere with successful dissemination of their work. Fonts not mentioned above must be provided by the author to the Editor concerned and to the journal. Embedded graphics or Postscript are not currently accepted. REFERENCES AND BIBLIOGRAPHY STYLES When you want to refer to Theorem A (which will not be called that in the TAC style) of Section 4.3, refer to it as Theorem~\ref{thmA} of Section~\ref{mainth}. The labels you use are totally arbitrary, of course, so long as they are not reused in the same paper. Use of symbolic labels allows you to insert or delete material without having to renumber everything or to wind up with sections or theorems bis. The ~, by the way, is an unbreakable space so that the theorem or section number does not get separated from the word Theorem or Section. This is considered poor style, although it is not terribly important. It is also an element of good style to capitalize the words Section and Theorem when followed by an explicit reference. However, they are not capitalized in such phrases as "next section" and "the main theorem". If BiBTeX is used with LaTeX, bibliographies must be BiBTeXed and .bbl files appended to the source file. No .bib files will be accepted. References may use the standard BiBTeX styles or the two bibliography styles that TAC supports. We recommend the first TAC style. It is much more useful for the reader since it puts citations like [Grothendieck, 1957] in your text (you can probably already guess the reference) and the reference in the form \item A. Grothendieck (1957), Quelques points d'algebre homologiques, T\^ohoku Math. J. \em{3}, 120-221. You get the first style by preceding your references with \begin{references} and ending the list of \items with \end{references} The second style is traditional and puts [4] into your paper with the reference in the traditional form \item A. Grothendieck, Quelques points d'algebre homologiques, T\^ohoku Math. J. \em{3} (1957), 120-221. To obtain it use \begin{references*} \item ... \end{references*} except you will almost surely want to use \bibitem, allowing you to put in a symbolic label. A FINAL POINT Although these instructions are specific to TAC, they should go a long way towards making your papers usable by any journal that is serious about using author-supplied TeX. From rrosebru@mta.ca Wed Jan 26 13:18:42 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA18278 for categories-list; Wed, 26 Jan 2000 11:31:40 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Wed, 26 Jan 2000 15:32:49 +0100 (MET) Message-Id: <200001261432.PAA00407@agaric.ens.fr> From: "Martin H. Escardo" To: categories@mta.ca Subject: categories: Re: Freyd's couniversal characterization of [0,1] In-Reply-To: References: <200001241914.UAA23504@agaric.ens.fr> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Andrej Bauer writes: > I can answer this for equilogical spaces. > > The functor F: Bi[Equ] ---> Bi[Equ] has a final coalgebra. It > is the equilogical space (C, ~) where C is the Cantor space > > C = 2^N = infinite sequences of 0's and 1's > > and ~ is the equivalence relation defined by > > a ~ b iff r(a) = r(b) > > where r: C --> [0,1] is defined by > > r(a) = \sum_{k=0}^\infty a_k / 2^{k+1} This is interesting in connection with some previous discussion in this list on "definability" of the mid-point operation "by coinduction". As it is well known, the mid-point operation is not continuously realizable via binary expansions with the Cantor topology. (As Andrej Bauer and other people have mentioned signed-digit binary expansions in this discussion, let me emphasize that, in contrast to the above situation, all continuous functions [-1,1]^n->[-1,1] are continuously realizable via signed-digit binary expansions with the Cantor topology. Put in another way, the space 3^N = (3^N)^n is projective over (the regular epimorphism) s:3^N->[-1,1], but the space 2^N is not projective over r:2^N->[0,1].) Martin Escardo From rrosebru@mta.ca Wed Jan 26 13:26:23 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA18029 for categories-list; Wed, 26 Jan 2000 11:31:18 -0400 (AST) X-Authentication-Warning: localhost.localdomain: andrej set sender to Andrej.Bauer@cs.cmu.edu using -f Cc: mhe@dcs.st-and.ac.uk To: categories@mta.ca Subject: categories: Re: Freyd's couniversal characterization of [0,1] References: <200001241914.UAA23504@agaric.ens.fr> From: Andrej Bauer Date: 26 Jan 2000 00:28:26 -0500 In-Reply-To: "Martin H. Escardo"'s message of "Mon, 24 Jan 2000 20:14:36 +0100 (MET)" Message-ID: Lines: 91 User-Agent: Gnus/5.0803 (Gnus v5.8.3) XEmacs/20.4 (Emerald) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: "Martin H. Escardo" writes: > It would be interesting to test Freyd's couniversal characterization > of the unit interval in many other categories. > > Here I test it in Top, the category of topological spaces and > continuous maps, and various full subcategories, where one would hope > to get the unit interval with the Euclidean topology. > > ---------------------------------------------------------------------- > Summary of the outcome of some tests: > > (1) In Top, the final coalgebra for Freyd's functor exists. Its > underlying object, however, is an indiscrete space (unsurprisingly). > > (2) In the category of T0 spaces, it doesn't exist. > > (3) In the category of normal spaces it does exist, and, as one > would hope, its underlying object is indeed the unit interval with the > Euclidean topology. > > See remark below for weakening normality in (3) as much as possible. > ---------------------------------------------------------------------- > Arguments follow. > > [text deleted] >> ---------------------------------------------------------------------- > Question: What does one get in full subcategories of locales and of > equilogical spaces? I can answer this for equilogical spaces. The functor F: Bi[Equ] ---> Bi[Equ] has a final coalgebra. It is the equilogical space (C, ~) where C is the Cantor space C = 2^N = infinite sequences of 0's and 1's and ~ is the equivalence relation defined by a ~ b iff r(a) = r(b) where r: C --> [0,1] is defined by r(a) = \sum_{k=0}^\infty a_k / 2^{k+1} (This equivalence relation can easily be defined without reference to the closed interval [0,1].) Thus, the final coalgebra is the _(unsigned) binary digit representation_ of the closed interval [0,1]. The structure map d: (C,~) ---> F(C,~) is induced by the canonical isomorphism C ---> C + C = 2 x C. Unfortunately, this closed interval is not what we would hope for. Ideally, we would want the _signed_ binary digit representation of the interval [-1,1], i.e., the space ({-1,0,1}^N, :=:) where :=: is defined by a :=: b iff s(a) = s(b) s(a) = \sum_{k=0}^\infty a_k / 2^{k+1} We want this because the real numbers object in Equ is the built from the _signed_ representation of reals. I do not see how to adapt the construction so that it yields the signed representation. We would have to "glue" more than just a couple of points. But how do we say what should be glued, without reference to [0,1] or C? Let me explain briefly why (C, ~) is the final coalgebra. In Equ, in the pushout 1 -------> X | | | | | | | | V V X -------> FX the underlying space of FX is |FX| = |X| + |X|. This is a "small" but crucial difference between Top and Equ. We can first find the final coalgebra in Top_0 for the functor A --> A + A, which is the Cantor space C, and then compute the equivalence relation on C. In this case it is easy to verify that all the continuous maps obtained from the coalgebraic structure of C actually preserve the equivalence relations. By the way, the two distinguished points of (C, ~) are 0^\infty and 1^\infty, of course (and it doesn't matter, since C is homogeneous). -- Andrej Bauer From rrosebru@mta.ca Thu Jan 27 10:45:03 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA24380 for categories-list; Thu, 27 Jan 2000 09:19:31 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Thu, 27 Jan 2000 13:25:25 +0100 (MET) Message-Id: <200001271225.NAA03856@agaric.ens.fr> From: "Martin H. Escardo" To: categories@mta.ca Subject: categories: re: Freyd's couniversal characterization of [0,1] In-Reply-To: <200001241914.UAA23504@agaric.ens.fr> References: <200001241914.UAA23504@agaric.ens.fr> Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: The following is of course rather unpleasent: > (1) In Top, the final coalgebra for Freyd's functor exists. Its > underlying object, however, is an indiscrete space (unsurprisingly). This can be fixed by choosing a slightly different category of bipointed objects. Define a *regularly bipointed object* to be an object X with two distinguished points x0,x1:1->X such that [x0,x1]:1+1->X is regular mono. Then the terminal coalgebra for Freyd's functor is 1 iff 1+1=1. With the restriction to regularly bipointed topological spaces, the statement (1) becomes false because the two-point discrete space 1+1 is not homeomorphically embeded as a subspace of any indiscrete space. Hopefully, there isn't a final coalgebra in RegBi(Top), but I don't see any if there is, it cannot be the Euclidean interval. My previous proof of (2) doesn't work with the proposed modification, but this should still hold. The argument for (3) is undisturbed. > (2) In the category of T0 spaces, it doesn't exist. > > (3) In the category of normal spaces it does exist, and, as one > would hope, its underlying object is indeed the unit interval with the > Euclidean topology. Martin Escardo From rrosebru@mta.ca Thu Jan 27 16:44:24 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id OAA00946 for categories-list; Thu, 27 Jan 2000 14:43:16 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f From: Application Asm Date: Thu, 27 Jan 2000 05:14:55 +0100 (MET) Message-Id: <200001270414.FAA27538@tec34.ethz.ch> To: categories@mta.ca Subject: categories: call for participation: ASM2000, March 19th - March 24th X-Sun-Charset: ISO-8859-1 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: -> We apologize if you received multiple copies <- ______________________________________________________________ _______ _______ _______ Call for Participation, Preliminary Program _______ _______ _______ _______ ASM2000 _______ _______ _______ _______ http://www.tik.ee.ethz.ch/~asm/2000 _______ _______ Monte Verita, Switzerland _______ _______ March 19th - 24th 2000 _______ ______________________________________________________________ In March 2000, an Abstract State Machine (ASM) Workshop will be held at Monte Verita, Switzerland. The aim of the workshop is to bring together domain-experts using ASMs as practical specification formalisms and theore- ticians using ASMs as formal starting point for their investi- gations, as well as people generally interested in ASMs. See http://www.eecs.umich.edu/gasm for more info on ASMs. The technical program consists of invited lectures, tutorials, presentations of refereed papers, and software demonstrations. A significant part of the time will be devoted to discussions. Arrival is on Sunday afternoon, June 19th, and the workshop program will end on Friday noon, June 24th. A limited number of grants covering registration and part of travel costs are available for undergraduate students. Applications shall include a short CV and resumee of scientific interests. ______________________________________________________________ _______ _______ _______ Important Dates _______ ______________________________________________________________ Grant applications deadline : February 15th Registration deadline : March 1st Earlier registrants get nicer rooms with view over lake and mountains! ASM2000 is just before ETAPS'2000 (Berlin, March 25-April 2,2000) so that attendance to both events can be suitably combined. ______________________________________________________________ _______ _______ _______ Location _______ ______________________________________________________________ Monte Verita served for over hundred year as a boiling meeting place for a variety of movements, ranging from naturalism, over anarchism, to various artistic tendencies. (see http://http://www.csf-mv.ethz.ch/Official/MonteVerita/History.html) The workshop takes place in the newly restored historic Bauhaus buildings, situated in a scenic park with a marvelous view onto the lake Lago Maggiore and the mountains. A 10 minutes walk away the participants can take advantage of Ascona, a picturesque medieval village on the shore of a splendid and sunny bay. (see http://www.ascona.ch/etale.htm) Ascona and the Monte Verita are situated in the heart of Europe, easily accessible from Milano, Italy and Zurich, Switzerland. For travel instructions see http://www.csf-mv.ethz.ch/Official/Additional/Additional.html _______________________________________________________________ _______ _______ _______ Registration Form _______ _______________________________________________________________ Please fill out the registration form below and send it until March 1st to Monica Fricker at the address on the form (regular mail only, no e-mail or fax) to register for the workshop. =============================================================== Send to: Monica Fricker (e-mail/fax not acceptable) Institut TIK ETH Zentrum Gloriastrasse 35 CH-8092 Zurich Switzerland ph: +41-1-632-7035 fax: +41-1-632-1035 EMail: fricker@tik.ee.ethz.ch Please Print or Type: Name:__________________________________________________________ Last/Family First MI Affiliation:___________________________________________________ Address:_______________________________________________________ _______________________________________________________ City:_________________________ State or Region:________________ Zip/Postal code:___________________ Country:___________________ Daytime Phone:_____________________ Fax Number:________________ Email:_________________________________________________________ Do you have any special needs?_________________________________ (special meals, access, etc.) Please circle appropriate fee * Workshop Registration, Accommodation, and Full Board: Student Regular Dollar $ 310 $ 510 Swiss Francs CHF 465 CHF 765 Charges: (please fill out) Total Enclosed: ________ (Swiss Francs (CHF)) PAYMENT MUST BE ENCLOSED: BANK-TO-BANK-TRANSFER (INTERNATIONAL MONEY ORDER) MUST BE DRAWN ON THE FOLLOWING BANK ACCOUNT: SCHWEIZERISCHE NATIONALBANK, BERN BC: 110 Acc.#: 1530-5-30-ETHZ Credit: ASM97 1-67-234-97 E_MAIL REGISTRATIONS CANNOT BE ACCEPTED BECAUSE WE NEED TO HAVE SIGNATURES ON FILE. CHECKS NOT ACCEPTED. Method of Payment ______ BANK-TO-BANK-TRANSFER ______ VISA ______ MASTERCARD ______ AMERICAN EXPRESS ______ DINERS CLUB Credit Card Number:____________________________________________ Exp. Date:____________________ Cardholder Name: ______________________________________________ Exactly as it is printed on the card Date:___________Signature:_____________________________________ We will have to bill no-show registered persons in full. Sorry, we cannot accept cancellations after March 1st, and refunds for cancellations before March 1st may take several months to process. _______________________________________________________________ _______ _______ _______ Program _______ _______________________________________________________________ Discussion sessions, ad hoc meetings, .... Invited Talks: -------------- Andreas Blass, Univ. of Michigan "Pure Mathematics and ASM's." Egon Börger, Univ. of Pisa "Composition and Structuring Principles for ASMs" Gerhard Goos, Univ. of Karlsruhe title to be anounced Martin Odersky, EPFL Lausanne "Functional Nets as a Composition Method for ASM's" Wolfgang Reisig, Humbold Univ. Berlin "Towards a Distributed ASM Thesis" Natarajan Shankar, SRI International "Symbolic Analysis of Transition Systems" Tutorials: ---------- Tutorials include tool-demonstrations and hands-on experience with the used tools. Infrastructure includes 12 SUN-workstations. Uwe Glaesser, Giuseppe del Castillo "Specifying Concurrent Systems with ASMs" The ASM-workbench is introduced and used for experiments with concurrent systems. Harald Ruess, ... , Natarajan Shankar "Verifying ASMs with PVS" The basic features of the PVS proof development system are introduced and demonstrated. Matthias Anlauff, Philipp Kutter, Alfonso Pierantonio "Developing Domain Specific Languages" The Gem-Mex system is used to prototype and visualize small domain specific languages with ASM semantics. Industrial Applications: ------------------------ Peter Paeppinghaus and Joachim Schmid, Siemens AG "Report about a practical application of ASMs in Software Design" Wolfram Schulte, Microsoft Research "ASM applications in industrial research and development" Presentations: -------------- M. Anlauff "Xasm - An Extensible, Component-Based Abstract State Machines Language" D. Beauquier and A. Slissenko "Verification of Timed Algorithms: Gurevich Abstract State Machines versus First Order Timed Logic" A. Blass, Y. Gurevich and J. Van den Bussche "Abstract state machines and computionally complete query languages" E. Boerger, A. Cavarra, and E. Riccobene "An ASM semantics for UML Activity Diagrams and UML State Machines" S.C. Cater and J.K. Huggins "An ASM Dynamic Semantics for Standard ML" J. Cohen and A. Slissenko "On Verification of Refinements of Timed Distributed Algorithms" R. Eschbach, U. Glaesser, R. Gotzhein, A. Prinz "The Semantics of Programming Languages: A transformational operational approach using Abstract State Machines" V.O. Di Iorio, R. da Silva Bigonha, and M. Maia "A Self-Applicable Partial Evaluator for ASM" A. Gargantini and E. Riccobene "Encoding Abstract State Machines in PVS" Y. Gurevich and D. Rosenzweig "Partially Ordered Runs: a Case Study" Y. Gurevich, W. Schulte, and C. Wallace "Investigating Java concurrency using Abstract State Machines" A. Heberle, W. Loewe, and W. Zimmermann "On Modular Definitions and Implementations of Programming Languages using Order-Sorted Partial Abstract State Machines" J.K. Huggins and W. Shen "The Static and Dynamic Semantics of C" B. Intrigila, G.D. Penna, and D. Ciccomartino "Extending Boerger's JVM Model to Compile Safe C++ Code: 1. The Pointers' Problem" J.W. Janneck and P.W. Kutter "Mapping Automaton - Simple Abstract State Machines" C. Pahl "Towards an Action Refinement Calculus for Abstract State Machines" H. Rust "Hybrid Abstract State Machines: Using the Hyperreals for Describing Continuous Changes in a Discrete Notation" J. Teich, P.W. Kutter, and R. Weper "Description and Simulation of Microprocessor Instruction Sets Using ASMs" K. Winter "Methodology for Model Checking ASM: Lessons learned from the FLASH Case Study" M. Spielmann "Model Checking Abstract State Machines and Beyond" A.V. Zamulin "Specifications In-the-large by Typed ASMs" A.V. Zamulin "Generic Facilities in Object-Oriented ASMs" _______________________________________________________________ _______ _______ _______ Organization _______ _______________________________________________________________ The workshop is sponsored by the Swiss Federal Institute of Technology, Microsoft Research, and BlueCapital. Organizers: Yuri Gurevich, Microsoft Research, Redmond, Washington Philipp W. Kutter, Federal Institute of Technology, Zürich Martin Odersky, Federal Institute of Technology, Lausanne Lothar Thiele, Federal Institute of Technology, Zürich From rrosebru@mta.ca Thu Jan 27 16:44:46 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA15821 for categories-list; Thu, 27 Jan 2000 15:11:08 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Reply-To: From: "Al Vilcius" To: Subject: categories: slogans Date: Wed, 26 Jan 2000 10:14:37 -0500 Message-ID: <000001bf6810$0fc38320$43925ad1@default> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 1 (Highest) X-MSMail-Priority: High X-Mailer: Microsoft Outlook 8.5, Build 4.71.2173.0 Importance: High In-Reply-To: X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211 Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: As a bit of a fun project, I would like to put together a collection of slogans, and am asking for contributions. Such a collection may or may not turn out to be "useful", but at least it will be amusing. I'm thinking of a slogan (apart from being a Scottish Highland war-cry) as a pithy little phrase or saying or motto or truism ..., just short of being poetry, that can tweak the neural pathways to follow a previously traveled path of understanding. Slogans tend to be little gems, often found in the folklore, but sometimes published, such as the 5 slogans in Jim Lambek & P. Scott's "Intro to higher order categorical logic" - these are: I: many objects of interest in mathematics congregate in concrete categories. II: many objects of interest to mathematicians are themselves small categories. III: many objects of interest to mathematicians may be viewed as functors from small categories to Sets. IV: many important concepts in mathematics arise as adjoints, right or left, to previously known functors. V: many equivalence and duality theorems in mathematics arise as an equivalence of fixed subcategories induced by a pair of adjoint functors. I think there are many more such gems; I like (and use) the one that says: the arrows always go through the limit. - I attribute this one to Armin Frei circa 1971 at UBC. Another really good one is: adjoints are the unity and identity of opposites. - I attribute this one to Bill Lawvwere Here are a couple more, from the physics of information: * there is no information without representation. * there is no processing without a process. - attributed to Benjamin Schumacher of Kenyon College. Each slogan can explode into rich and meaningful ideas, sort of the "url's of the mind" (if you like that kind of cyber-geek talk). Anyway, I hope the intention is clear, and that everyone will contribute their favourites as well. Please either post a response or send to me directly (no flames please), along with appropriate credit if known; I will assemble, and depending on how it goes, make the collection available. Could be fun and interesting - I look forward to your responses. Best regards to all .... Al /\ / Al R. Vilcius, Canada / \ / mailto:al.r@vilcius.com /--->\ / Tel./FAX (905) 854-3342 /3371 / \/ web site: http://www.VILCIUS.com From rrosebru@mta.ca Thu Jan 27 17:27:06 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id PAA15197 for categories-list; Thu, 27 Jan 2000 15:30:43 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Thu, 27 Jan 2000 14:28:57 -0500 (EST) From: James Stasheff To: categories@mta.ca Subject: categories: terminology Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: Has terminology settled down? I can recall seeing various terms for ``simplicial object without degeneracies'' .oooO Jim Stasheff jds@math.unc.edu (UNC) Math-UNC (919)-962-9607 \ ( Chapel Hill NC FAX:(919)-962-2568 \*) 27599-3250 http://www.math.unc.edu/Faculty/jds From rrosebru@mta.ca Thu Jan 27 23:51:28 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA19263 for categories-list; Thu, 27 Jan 2000 22:44:48 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Thu, 27 Jan 2000 16:04:10 -0500 From: Paul Glenn Subject: categories: Re: terminology To: James Stasheff Cc: categories@mta.ca Reply-to: glenn@cua.edu Message-id: <3890B2C9.EB35F625@cua.edu> Organization: CUA - Department of Mathematics MIME-version: 1.0 X-Mailer: Mozilla 4.51 (Macintosh; I; PPC) Content-type: text/plain; charset=us-ascii Content-transfer-encoding: 7bit X-Accept-Language: en References: Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: How about "face complex"? James Stasheff wrote: > > Has terminology settled down? > I can recall seeing various terms for > ``simplicial object without degeneracies'' > > .oooO Jim Stasheff jds@math.unc.edu > (UNC) Math-UNC (919)-962-9607 > \ ( Chapel Hill NC FAX:(919)-962-2568 > \*) 27599-3250 > > http://www.math.unc.edu/Faculty/jds -- Paul Glenn Department of Mathematics Catholic University of America From rrosebru@mta.ca Fri Jan 28 09:35:27 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id IAA15288 for categories-list; Fri, 28 Jan 2000 08:23:03 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 07:02:33 -0500 (EST) From: James Stasheff To: categories@mta.ca Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Subject: categories: re: terminology Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: So far the clear front runner is `face complex' Thanks to all the nominators. Grandis points out why the historical semi-simplicial won't fly for at least another generation. .oooO Jim Stasheff jds@math.unc.edu (UNC) Math-UNC (919)-962-9607 \ ( Chapel Hill NC FAX:(919)-962-2568 \*) 27599-3250 http://www.math.unc.edu/Faculty/jds From rrosebru@mta.ca Fri Jan 28 09:36:19 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id IAA16473 for categories-list; Fri, 28 Jan 2000 08:21:52 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Fri, 28 Jan 2000 10:57:40 +0100 To: categories@mta.ca, James Stasheff From: grandis@dima.unige.it (Marco Grandis) Subject: categories: Re: terminology Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: J. Stasheff wrote: >Has terminology settled down? >I can recall seeing various terms for >``simplicial object without degeneracies'' I am afraid it has not. In my opinion, it should be called 'semi-simplicial object', consistently with the original terminology in Eilenberg-Zilber (see references below). Such a term has been adopted in Weibel's text on homological algebra (1994). But there seems to be some opposition. ___ I hope the following reconstruction of terminology is correct. 1. What is now called a simplicial object was introduced by Eilenberg and Zilber (1950); they use: (a) [already existing] 'simplicial complex' = set with distinguished parts; (b) [new term] 'semi-simplicial complex' = graded set with faces; (c) [new term] 'complete s.s. complex' = graded set with faces and degeneracies; 2. Later, notion (c) was recognised as more important than (b) and called 'semi-simplicial complex', leaving (b) without any standard name. 3. Since May's book (1967) at least, notion (c) gradually settled down as 'simplicial set', generalised to 'simplicial object' in a category; this is now standard. 4. It should now be natural to use a similar term, 'semi-simplicial object (possibly: set)' for (b), i.e. a 'simplicial object without degeneracies' (as in Weibel 1994). This is consistent with the original use in Eilenberg-Zilber and gives a non-ambiguous set of terms for the three notions recalled: (a) 'simplicial complex' (also: combinatorial complex) (b) 'semi-simplicial object (set)' (c) 'simplicial object (set)' However, I used myself this terminology in a paper published in '97 and had strong reactions from people attached to the terminology in use between 50's and '60s (point 2 above). ___ References: S. Eilenberg - J.A. Zilber, Semi-simplicial complexes and singular homology, Ann. of Math. 51 (1950), 499-513. J.P. May, Simplicial objects in algebraic topology, Van Nostrand 1967. C.A. Weibel, An introduction to homological algebra, Cambridge Univ. Press, Cambridge, 1994. ___ With best regards Marco Grandis Dipartimento di Matematica Universita' di Genova via Dodecaneso 35 16146 GENOVA, Italy e-mail: grandis@dima.unige.it tel: +39.010.353 6805 fax: +39.010.353 6752 http://www.dima.unige.it/STAFF/GRANDIS/ ftp://pitagora.dima.unige.it/WWW/FTP/GRANDIS/ From rrosebru@mta.ca Fri Jan 28 09:44:06 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id IAA12711 for categories-list; Fri, 28 Jan 2000 08:23:56 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 07:21:26 -0500 (EST) From: James Stasheff To: categories@mta.ca Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Subject: categories: abcd=cba Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: The pentagon relation abc=de occurs all over the place. I've just come across abcd = cba for the first time. Look familiar? .oooO Jim Stasheff jds@math.unc.edu (UNC) Math-UNC (919)-962-9607 \ ( Chapel Hill NC FAX:(919)-962-2568 \*) 27599-3250 http://www.math.unc.edu/Faculty/jds From rrosebru@mta.ca Sat Jan 29 23:09:43 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA01705 for categories-list; Sat, 29 Jan 2000 22:12:57 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 17:42:52 +0000 (GMT) From: Ronnie Brown To: CATEGORIES@mta.ca Subject: categories: Re: slogans In-Reply-To: <000001bf6810$0fc38320$43925ad1@default> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: How do you like: Higher dimensional algebra supplies algebraic inverses to subdivision, for application to local-to-global problems. (That has been the intention of our programme since the mid-1960's.) Ronnie Brown On Wed, 26 Jan 2000, Al Vilcius wrote: > As a bit of a fun project, I would like to put together a collection of > slogans, and am asking for contributions. Such a collection may or may not > turn out to be "useful", but at least it will be amusing. > New popularisation project http://www.bangor.ac.uk/ma/CPM/rpamath/overall.htm Help sought! School of Informatics, Mathematics Division, University of Wales, Bangor Dean St., Bangor, Gwynedd LL57 1UT, United Kingdom Tel. direct:+44 1248 382474|office: 382475 fax: +44 1248 361429 World Wide Web: home page: http://www.bangor.ac.uk/~mas010/ (Links to survey articles: Higher dimensional group theory Groupoids and crossed objects in algebraic topology) Symbolic Sculpture and Mathematics: http://www.bangor.ac.uk/SculMath/ Mathematics and Knots: http://www.bangor.ac.uk/ma/CPM/exhibit/welcome.htm From rrosebru@mta.ca Sat Jan 29 23:11:25 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA05434 for categories-list; Sat, 29 Jan 2000 22:17:15 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 17:02:48 -0500 (EST) From: James Stasheff To: categories@mta.ca Subject: categories: 2 on terminology (fwd) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: .oooO Jim Stasheff jds@math.unc.edu (UNC) Math-UNC (919)-962-9607 \ ( Chapel Hill NC FAX:(919)-962-2568 \*) 27599-3250 http://www.math.unc.edu/Faculty/jds ---------- Forwarded message ---------- Date: Fri, 28 Jan 2000 12:26:36 EST From: DON DAVIS To: toplist Subject: 2 on terminology Two similar responses regarding simplicial terminology.....DMD ______________________________________________________ Date: Fri, 28 Jan 2000 08:56:36 -0600 (CST) From: Peter May Subject: "Delta sets" Once upon a time, people doing category theory and algebraic topology overlapped with people doing geometric topology and algebraic topology. There is a large literature of $\triangle$-sets, or $\delta$-sets, which are precisely simplicial sets without degeneracy operations. I believe the term was introduced in the pair of papers listed in MathSciNet as "$\triangle$-sets. I II", by Colin Rourke and Brian Sanderson. Both papers were published in 1971, in the Quarterly Journal of Mathematics. The main point is that use of delta sets is essential to the theory of block bundles and thus to PL topology. Peter May ______________________________________________________________ Date: Fri, 28 Jan 2000 15:12:58 GMT From: Brian Sanderson Subject: Re: terminology. Delta sets. J. Stasheff wrote: >Has terminology settled down? >I can recall seeing various terms for >``simplicial object without degeneracies'' Colin Rourke and I called these sets Delta sets. Unfortunately you might have to look for "$\triangle" to find them. Prior to the two papers below they were a neglected curiosity. We needed them when block bundles emerged. I don't know how current the terminology is now. Brian Sanderson [7] 45 #9328 Rourke, C. P.; Sanderson, B. J. $\triangle $-sets. II. Block bundles and block fibrations. Quart. J. Math. Oxford Ser. (2) 22 (1971), 465--48 5. (Reviewer: E. B. Curtis) 55F60 [8] 45 #9327 Rourke, C. P.; Sanderson, B. J. $\triangle $-sets. I. Homotopy theory. Quart. J. Math. Oxford Ser. (2) 22 (1971), 321--338. (Reviewer: E. B. Curtis) 55F60 (55D99) From rrosebru@mta.ca Sat Jan 29 23:12:35 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA03427 for categories-list; Sat, 29 Jan 2000 22:08:10 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Message-Id: <200001281237.AA00902@menthe.ens.fr> Content-Type: text/plain Mime-Version: 1.0 (NeXT Mail 4.2mach_patches v148.2) From: Giuseppe Longo Date: Fri, 28 Jan 2000 13:37:21 +0100 To: categories@mta.ca Subject: categories: Re: slogans Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: ... about adding slogans: "there is no mathematics without structures" and "there are no structures without transformations (between structures)" In stating this, I would go back to (Gauss and) Reimann (and Klein). This was a turning point of last century mathematics. Geometry is the analysis of (possibly) curved space and the unity of geometries is found on the notion of transformation (over manifolds, say: continuous, differentiable ...). Mathematics is no more found (only) on "quantities", since ratios of length and of angles, at the heart of Euclidean geometry, are not preserved in non-euclidean frames (their group of automorphisms are not closed under omotheties). Category Theory is the theory which inherited this fantastic broadening of perspective. --Giuseppe Longo Lab. "Jacques Herbrand" CNRS et Ecole Normale Superieure (Postal addr.: LIENS 45, Rue D'Ulm 75005 Paris (France) ) http://www.dmi.ens.fr/users/longo e-mail: longo@di.ens.fr (tel. ++33-1-4432-3328, FAX 4432-2080) Upon kind permission of the M.I.T. Press, the book below is currently downloadable from Longo's web page above (its n-th edition is out of print...): Andrea Asperti and Giuseppe Longo. Categories, Types and Structures: an introduction to Category Theory for the working computer scientist. M.I.T.- Press, 1991. (pp. 1--300). From rrosebru@mta.ca Sat Jan 29 23:43:19 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA04354 for categories-list; Sat, 29 Jan 2000 22:14:01 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 14:56:53 -0500 (EST) From: Peter Freyd Message-Id: <200001281956.OAA28133@saul.cis.upenn.edu> To: categories@mta.ca Subject: categories: integrals Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: Let I be a closed interval and let C(X) denote the bipointed midpoint algebra of continuous functions from a space X to I. I would not have guessed the following: 1. Any map from C(X) to C(Y) that preserves midpoints, top, and bottom is monotonic and preserves constant functions. The order preservation is an immediate consequence of: f =< g iff there exists h such that f|top = g|h If we specialize to the case that X and Y are single points, the order preservation implies the only map from I to I that preserves midpoints, top and bottom, is the identity map (after first noticing that it must have a dense subset of fixed points corresponding to the dyadic rationals). Let I -> C(X) be the "K-map" that assigns constant maps. For any y:Y let C(Y) -> I be its evaluation map. Then for any map C(X) -> C(Y) that preserves midpoints, top, and bottom we have that I -> C(X) -> C(Y) -> I is the identity map. And from that we can easily conclude that C(X) -> C(Y) preserves constant maps. In a 22 Dec posting I said that the "mean-value" function M:C(I) -> I can be characterized from its order preservation together with what it does to constant functions and MxM C(I v I) --> C(I + I) --> C(I) x C(I) ---> I x I C(F) | | m v v M C(I) -----------------------------------> I where F:I -> I v I is the coalgebra structure and m is the midpoint operation. I went on to say that if C(F) is inverted then this diagram can be read as a fixed-point definition of M: "It's the unique fixed-point of an operator acting on the set of all those order-preserving maps from C(I) to R that do the right thing on constant functions." It's much better to change the R to I and say just that it's acting on the set of bipointed midpoint-algebra homomorphisms. To recapitulate (using \ for lambda, T for top, B for bottom): 2. The mean-value operator, M:C(I) --> I, is the unique map such that: M(\x.B) = B M(\x.T) = T (Mf)|(Mg) = M(\x.(fx)|(gx)) Mf = (M(\x.f(B|x)))|(M(\x.f(x|T))) No inequalities, no limits, only equations. Let me take the occasion to do a little clean-up. In a 31 Dec posting I gave a curse-of-analysis proof for: 3. Midpoint-preserving functions between intervals are monotonic. Here's a much better proof. Monotonicity is equivalent to the preservation of betweenness. Suppose f is a midpoint-preserving map between intervals. It's conceptually useful to take the target to be, instead, the real line and show that a failure to preserve betweenness forces the values of f to be unbounded. So let a,b,c be points in the source interval with b between a and c which fact will be denoted as {a.b.c} and suppose that fb is not between fa and fc. Without loss of generality we can assume that {fa.fc.fb}. There exists {a.b'.c} such that either b = a|b' or b = c|b'. Each of the equations fb = fa|fb' and fb = fc|fb' implies {fa.fc.fb'}. So {a.b'.c} is still an example but the first equation implies that the distance from fc to fb' is twice -- and the second equation implies it is _at least_ twice -- the distance from fc to fb. By iteration we may thus increase that distance beyond any bound. A point that the previous proof didn't really cover is dispatched by this corollary: 4. Midpoint-preserving functions between intervals are either one-to-one or constant. Suppose a and c are distinct but fa = fc. If there's c' such that c = a|c' then we may infer that fa = fc'. By replacing c with c' in this manner as long as possible we may assume that a and c are such that there is no solution to the equation c = a|x and from that we may infer that if c' is chosen to be the endpoint such that {a.c.c'} then there is {a,b,c} such that c = b|c'. By the last result we have fa = fb = fc hence fc = fb = fc'. Thus we may assume that a and c are distinct with fa = fc and c an endpoint. Similarly we may assume that a is an endpoint and finish by applying, once again, the last result. Besides injectivity we have this corollary on surjectivity obtained by combining 1 and 3: 5. The image of any midpoint preserving function between intervals is a closed interval. PS >From the proof of 1 it is clear that order preservation doesn't require preservation of bottom. A similar proof uses preservation of bottom instead of top, but if both conditions are dropped the map needn't even be monotonic. Let I = [-1,1] and let C(I) -> I be the map that sends f to f(-1)|(-f1). It sends all constant functions to 0, it sends the identity map to -1 and it sends the negating map to 1.) The proof of 3 suggests that if the target interval is replaced by the reals then there do exist midpoint-preserving maps that are not monotonic. And that is, indeed, the case in the presence of the axiom of choice: view the reals as a rational vector-space and count the number of endomorphisms (each of which preserves midpoints) to find that there are 2^{2^N} of them. But there are only 2^N monotonic self maps (midpoint preserving or not). Do we need the axiom of choice? If, instead, we add the axiom of measurability, then the counterexamples disappear: let f be a measurable midpoint-preserving map from R to R; we can easily specialize to the case that f0 = 0, hence f is a measurable group endomorphism; for any real a consider the induced group homomorphism from R/aZ to R/(fa)Z; any measurable group character is continuous and that's enough to force f to be continuous. From rrosebru@mta.ca Mon Jan 31 11:43:01 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id JAA18478 for categories-list; Mon, 31 Jan 2000 09:46:41 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Fri, 28 Jan 2000 18:44:45 +0100 From: Doris Faehndrich To: cfpart-l@iks.cs.tu-berlin.de, etaps-news@cs.tu-berlin.de Subject: categories: ETAPS 2000 - Call for Participation Message-ID: <20000128184444.G20372@keiner.cs.tu-berlin.de> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i Sender: cat-dist@mta.ca Precedence: bulk Status: RO X-Status: (Sorry, if you receive multiple copies of this Call. Doris Faehndrich) ----------------------------------------------------------------- ETAPS 2000 - EUROPEAN JOINT CONFERENCES ON THEORY AND PRACTICE OF SOFTWARE Technical University of Berlin, March 25 - April 2, 2000 -------------------- CALL FOR PARTICIPATION ------------------------- Welcome to Berlin, welcome to ETAPS, the European Joint Conferences on Theory and Practice of Software, the european forum for academic and industrial researchers working on these topics! For 9 days you will be able to choose between 5 conferences with more than 120 regular papers and tool demonstrations covering a wide range of topics from theory and practice, 7 invited lectures, 10 tutorials, and 5 satellite events. -------------------------------------------------------------------- Please, check for details http://iks.cs.tu-berlin.de/etaps2000/ Use the option of online registration or one of the downloadable registration forms! -------------------------------------------------------------------- EARLY REGISTRATION UNTIL FEBRUARY 29, 2000 -------------------------------------------------------------------- Main Conferences, March 27 - March 31 ------------------------------------- CC 2000 International Conference on Compiler Construction Chair: David Watt (University of Glasgow, UK) ESOP 2000 European Symposium on Programming Chair: Gert Smolka (Saarland University, D) FASE 2000 Fundamental Approaches to Software Engineering Chair: Tom Maibaum (King's College London, UK) FOSSACS 2000 Foundations of Software Science and Computation Structures, Chair: Jerzy Tiuryn (University of Warsaw, PL) TACAS 2000 Tools and Algorithms for the Construction and Analysis of Systems, Chair: Susanne Graf (VERIMAG, Grenoble, F) Invited Speakers ---------------- Abbas Edalat (Imperial College, London, UK) ``A Data Type for Computational Geometry and Solid Modelling'' David Harel (The Weizmann Institute of Science, Rehovot, IL) ``From play-in scenarios to code: an achievable dream'' Martin Odersky (EPF Lausanne, CH) ``Functional nets'' Richard Mark Soley (OMG Object Management Group, USA) ``Memex isn't Enough'' Wladyslaw M. Turski (University of Warsaw, PL) ``An essay on software engineering at the turn of century'' Reinhard Wilhelm (Saarland University, D) ``Shape analysis'' Pierre Wolper (University of Liege, B) ``On the representation of constraints by automata in the verification of infinite systems'' Panel: ``Standard Components of the Shelf - Do they carry and need a (Formal) Standard Semantics?'' Chair: Herbert Weber (TU Berlin, D) Satellite Events ---------------- GRATRA - Joint APPLIGRAPH/GETGRATS Workshop on Graph Transformation Systems, Contact: Hartmut Ehrig (TU Berlin, D) March 25 - March 27 Invited Lecture by Grzegorz Rozenberg (University of Leiden, NL) ``DNA Computing in vivo and graph transformation'' (open for all ETAPS participants) CMCS - Workshop on Coalgebraic Methods in Computer Science Contact: Horst Reichel (TU Dresden, D) March 25 - March 26 CBS - International Workshop on Communication-Based Systems Contact: Guenter Hommel(TU Berlin, D) March 31 - April 1 INT - Integration of Specification Techniques with Applications in Engineering, Contact: Martin Grosse-Rhode(TU Berlin, D) March 31 - April 1 CoFI - Common Framework Initiative for Algebraic Specification and Development of Software Contact: Don Sannella (University of Edinburgh, UK) April 1 - April 2 Tutorials --------- XML for Software Engineers Andrea Zisman, Anthony Finkelstein (University College London, UK) March 25, p.m., half-day A tutorial on Maude Narciso Marti Oliet (Universidad Complutense, Madrid, E), Jose Meseguer (SRI International, USA) March 25, p.m., half-day Rigorous Requirements for Safety-Critical Systems: Fundamentals and Applications of the SCR Method Constance L. Heitmeyer (Naval Research Laboratory, USA) March 26, full-day Multi-Paradigm Programming Michael Hanus (RWTH Aachen, D) March 26, a.m., half-day Query-based Automated Debugging Mireille Ducasse (IRISA/INSA, F) March 26, p.m., half-day The Unified Modelling Language Perdita Stevens (University of Edinburgh, UK) April 1, full-day Swinging Types Peter Padawitz (University of Dortmund, D) April 1, a.m., half-day Tables and computation A.J.Wilder (University of Wales, UK) April 1, p.m., half-day SDL 2000 Joachim Fischer (HU Berlin, D), Andreas Prinz (Research Digital Media Systems GmbH, D), Eckhardt Holz (HU Berlin, D) April 2, full-day Software Metrology Basis Hans-Ludwig Hausen (GMD Bonn, D) April 2, a.m., half-day ------------------------------------------------------------------ ETAPS Steering Committee Don Sannella (Chairman, UK), Egidio Astesiano (I), Jan Bergstra (NL), Pierpaolo Degano (I), Hartmut Ehrig (D), Jose Luiz Fiadeiro (P), Marie-Claude Gaudel (F), Susanne Graf (F), Furio Honsell (I), Heinrich Hussmann (D), Stefan Jaehnichen (D), Paul Klint (NL), Tom Maibaum (UK), Tiziana Margaria (D), Ugo Montanari (I), Hanne Riis Nielson (DK), Fernando Orejas (E), Andreas Podelski (D), David Sands (S), Gert Smolka (D), Bernhard Steffen (D), Wolfgang Thomas (D), Jerzy Tiuryn (PL), David Watt (UK), Reinhard Wilhelm (D) Organizing Chairs: Bernd Mahr, Hartmut Ehrig, Peter Pepper, Stefan Jaehnichen, Radu Popescu-Zeletin Conference Address: ETAPS 2000, TU Berlin, Sekr. FR 6-10, Franklinstr. 28/29, D-10587 Berlin Germany Tel: ++49 30 314 -73540, Fax: -73622 Email: etaps2000@iks.cs.tu-berlin.de http://iks.cs.tu-berlin.de/etaps2000/ Registration Address: BWO Marketing Service GmbH Mohrenstr. 63-64 D-10117 Berlin-Mitte Germany Fax: ++49 30 22 66 84-64 Email: Etaps2000@BWO-Berlin.de -=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Doris Fähndrich: TU Berlin FB-13 Sekr. FR 5-6, Franklinstr. 28/29, 10587 Berlin, Tel: 030/31473436 -=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= From rrosebru@mta.ca Mon Jan 31 13:38:50 2000 -0400 Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id LAA24631 for categories-list; Mon, 31 Jan 2000 11:59:15 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f Date: Mon, 31 Jan 2000 10:55:10 -0500 (EST) From: Richard Blute Message-Id: <200001311555.KAA28003@castor.mathstat.uottawa.ca> To: categories@mta.ca Subject: categories: Grad positions available Sender: cat-dist@mta.ca Precedence: bulk Status: O X-Status: The Logic Team at the Math Department of the University of Ottawa announces that it anticipates having one or more openings in its graduate program beginning in September. These would be at either the Master's or Ph. D. level, and would come with funding in the form of tuition and an additional stipend. The team is run by Phil Scott and Rick Blute, and specializes in the following areas: -linear logic -categorical logic and proof theory -category theory, especially monoidal categories -logic and foundations of computer science We have close affiliations with the University of Ottawa School of Information Technology and Engineering, as well as the Category Theory Research Centre in Montreal, and our students have many opportunities to interact with the members of these institutions. The Math Department at the University of Ottawa has a wide range of research interests and provides an excellent environment for graduate study. Students here also have the advantage of living in one of the most beautiful cities in Canada, and the national capital. For further information, please visit our website at www.science.uottawa.ca/mathstat, or contact Rick Blute at rblute@mathstat.uottawa.ca or Phil Scott at phil@mathstat.uottawa.ca.