March 2007 - Categories - categories.org.au

Foundations?
by F W Lawvere 03 Sep '10

03 Sep '10

Down with "Foundations"! Up with algebra! Dear Friends, Presumably I am among those who are being "vilified" as "lovers of categories as foundation". By avoiding any precise definition, such a formulation might appeal to the widespread justified boredom induced by the past hundred years of "foundations as justification". Whenever I used the word "foundation" in my writings over the past forty years, I have explicitly rejected that reactionary use of the term and instead used the definition implicit in the work of my teachers Truesdell and Eilenberg. Namely, an important component of mathematical practice is the careful study of historical and contemporary analysis, geometry, etc. to extract the essential recurring concepts and constructions; making those concepts and constructions (such as homomorphism, functional, adjoint functor, etc.) explicit provides powerful guidance for further unified development of all mathematical subjects, old and new. What is the primary tool for such summing up of the essence of ongoing mathematics? Algebra! Nodal points in the progress of this kind of research occur when, as is the case with the finite number of axioms for the metacategory of categories, all that we know so far can be expressed in a single sort of algebra. I am proud to have participated with Eilenberg, Mac Lane, Freyd, and many others, in bringing about the contemporary awareness of Algebra as Category Theory Had it not been for the century of excessive attention given to the alleged possibility that mathematics is inconsistent, with the accompanying degradation of the F-word, we would still be using it in the sense known to the general public: the search for what is "basic". We, who supposedly know the explicit algebra of homomorphisms, functionals, etc. are long remiss in our duty to find ways to utilize those concepts also in guiding high school calculus. Best wishes, Bill Bibliography: - The Category of Categories as a Foundation for Mathematics, La Jolla conference 1965, Springer (1966) - Adjointness in Foundations, Dialectica, (1969), to be reprinted in TAC - Foundations and Applications: Axiomatization and Education, Bulletin of Symbolic Logic, (2003) vol 9, pp 213-224 - Sets for Mathematics, w/ Bob Rosebrugh, Cambridge Univ. Press, (2003) ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************

2 1

Full and faithful
by Robin Houston 03 Apr '07

03 Apr '07

A functor F: C -> D is full and faithful just when, for all categories X and functors G, H: X -> C, the whiskering action of F induces a bijection between [G, H] and [FG, FH] (where [G, H] denotes the set of natural transformations from G to H). Clearly this formulation makes sense in any bicategory. Is there a name for 1-cells with this property? Thanks! Robin

2 1

functions not polynomials
by Paul Taylor 29 Mar '07

29 Mar '07

Let f: Z x Z -> Z be a binary FUNCTION (in the sense of sets) on the integers, with the property that - for each x:Z, f(x,-) : Z -> Z is a (agrees with a unique) POLYNOMIAL, whose coefficients are functions of x; and similarly - for each y:Z, f(-,y) : Z -> Z is also a polynomial. Then f(x,y) was itself a polynomial in two variables. "You just use Newton's difference method to find the co..." .... unterexample. Taking N for simplicity first, consider the binomial coefficient (x,n) as an nth degree polynomial in x, ie (x,0) = 1 (x,1) = x (x,2) = x(x-1)/2 (x,3) = x(x-1)(x-2)/3! and so on. Newton's finite difference method provides the coefficients of these generating polynomials by taking successive differences (the finite analogue of successive derivatives). But then sum_n (x,n)(y,n) is a function NxN->N that is a polynomial in x for each y and vice versa but isn't itself a polynomial. None of the web pages that I found about this method was especially clear, so I'm not going to recommend any, but they are there if you want to look for them yourself. The more general method (as described on these pages, which is why I didn't think they were that good) takes differences from any sequence of points, not just 0, 1, 2, .... Hence, given any enumeration of a countable field K (this probably works for Z too) we can generalise both the method of fitting polynomials and the counterexample. Of course, since I'm a categorist, it was the categorical formulation that interests me. Any thoughts on that would be appreciated, despite the above failure of the simple example. In fact, I'd quite like to hear from any students of universal algebra out there who also know how monads encode algebraic theories, and might be willing to help as sparring partners for my present mad scheme. Paul Taylor

2 3

SOS 2007 - Final Call for Papers
by Rob van Glabbeek and Matthew Hennessy 29 Mar '07

29 Mar '07

Structural Operational Semantics 2007 An Affiliated Workshop of LICS 2007 and ICALP 2007 July 9, 2007, Wroclaw, Poland http://www.cse.unsw.edu.au/~rvg/SOS2007 Aim: Structural operational semantics (SOS) provides a framework for giving operational semantics to programming and specification languages. A growing number of programming languages from commercial and academic spheres have been given usable semantic descriptions by means of structural operational semantics. Because of its intuitive appeal and flexibility, structural operational semantics has found considerable application in the study of the semantics of concurrent processes. Moreover, it is becoming a viable alternative to denotational semantics in the static analysis of programs, and in proving compiler correctness. Recently, structural operational semantics has been successfully applied as a formal tool to establish results that hold for classes of process description languages. This has allowed for the generalisation of well-known results in the field of process algebra, and for the development of a meta-theory for process calculi based on the realization that many of the results in this field only depend upon general semantic properties of language constructs. This workshop aims at being a forum for researchers, students and practitioners interested in new developments, and directions for future investigation, in the field of structural operational semantics. One of the specific goals of the workshop is to establish synergies between the concurrency and programming language communities working on the theory and practice of SOS. Moreover, it aims at widening the knowledge of SOS among postgraduate students and young researchers worldwide. Specific topics of interest include (but are not limited to): * programming languages * process algebras * higher-order formalisms * rule formats for operational specifications * meaning of operational specifications * comparisons between denotational, axiomatic and SOS * compositionality of modal logics with respect to operational specifications * congruence with respect to behavioural equivalences * conservative extensions * derivation of proof rules from operational specifications * software tools that automate, or are based on, SOS. Papers reporting on applications of SOS to software engineering and other areas of computer science are welcome. History: The first SOS Workshop took place on the 30th of August 2004 in London as one of the satellite workshops of CONCUR 2004. Subsequently, SOS 2005 occurred on the 10th of July 2005 in Lisbon as a satellite workshop of ICALP 2005, and SOS 2006 on the 26th of August 2006 in Bonn as a satellite workshop of CONCUR 2006. A special issue of the Journal of Logic and Algebraic Programming on Structural Operational Semantics appeared in 2004; a special issue of Theoretical Computer Science dedicated to SOS 2005 is in press, and a special issue of Information & Computation on Structural Operational Semantics inspired by SOS 2006 is in preparation. INVITED SPEAKER: Pawel Sobocinski (Cambridge, UK) PAPER SUBMISSION: We solicit unpublished papers reporting on original research on the general theme of SOS. Prospective authors should register their intention to submit a paper by uploading a title and abstract via the workshop web page by: *** Friday 6 April 2007. *** Papers should take the form of a pdf file in ENTCS format [http://www.entcs.org/] whose length should not exceed 15 pages (not including an optional "Appendix for referees" containing proofs that will not be included in the final paper). We will also consider 5-page papers describing tools to be demonstrated at the workshop. Proceedings: Preliminary proceedings will be available at the meeting. The final proceedings of the workshop will appear as a volume in the ENTCS series. We may decide to arrange a special issue of an archival journal devoted to full versions of selected papers from the workshop. IMPORTANT DATES: * Submission of abstract: Friday 6 April 2007 * Submission: Sunday 15 April 2007 * Notification: Wednesday 9 May 2007 * Final version: Friday 25 May 2007 * Workshop: Monday 9 July 2007 * Final ENTCS version: Friday 10 August 2007. PROGRAMME COMMITTEE Luca Aceto (Aalborg, DK; Reykjavik, IS) Rocco De Nicola (Florence, IT) Rob van Glabbeek (NICTA, AU, co-chair) Reiko Heckel (Leicester, UK) Matthew Hennessy (Sussex, UK, co-chair) Bartek Klin (Warsaw, PL) Ugo Montanari (Pisa, IT) MohammadReza Mousavi (Eindhoven, NL; Reykjavik, IS) Prakash Panangaden (Montreal, CA) Grigore Rosu (Urbana-Champaign, IL, USA) Simone Tini (Insubria, I) Shoji Yuen (Nagoya, JP) CONTACT: sos2007(a)cs.stanford.edu WORKSHOP ORGANISERS: Rob van Glabbeek National ICT Australia Locked Bag 6016 University of New South Wales Sydney, NSW 1466 Australia Matthew Hennessy Department of Informatics University of Sussex Falmer, Brighton, BN1 9QN United Kingdom

1 0

A preprint on Weak cubical categories
by Marco Grandis 27 Mar '07

27 Mar '07

The following preprint is available on my server: M. Grandis, Higher cospans and weak cubical categories (Cospans in Algebraic Topology, I) Dip. Mat. Univ. Genova, Preprint 552 (2007). in pdf and ps: http://www.dima.unige.it/~grandis/wCub.pdf http://www.dima.unige.it/~grandis/wCub.ps Comments and suggestions are appreciated. Marco Grandis ---------------------- Abstract. We define a notion of weak cubical category, abstracted from the structure of n-cubical cospans x: \Lambda^n ---> X in a category X, where \Lambda is the 'formal cospan' category. These diagrams form a cubical set with compositions in all directions, which are computed with pushouts and behave 'categorically' in a weak sense, up to suitable comparisons. Actually, we work with a 'symmetric cubical structure', which includes the transposition symmetries, because this allows for a strong simplification of the coherence conditions. These notions will be used in subsequent papers to study topological cospans and their use in Algebraic Topology, from tangles to cobordisms of manifolds. We also introduce the more general notion of a multiple category, where - to start with - arrows belong to different sorts, varying in a countable family and symmetries must be dropped. The present examples seem to show that the symmetric cubical case is better suited for topological applications. Mathematics Subject Classifications: 18D05, 55U10 Key words: weak cubical category, multiple category, double category, cubical sets, spans, cospans. ----------------------

1 0

2cfc: CALCO-jnr 2007: CALCO Young Researchers Workshop, Bergen, Norway
by Monika Seisenberger 23 Mar '07

23 Mar '07

[Apologies for multiple copies] !!! PLEASE FORWARD TO PHD STUDENTS AND YOUNG RESEARCHERS !!! *------------------------------------------------------------------* * 2nd call for contributions * * * * CALCO-jnr 2007 * * * * CALCO-jnr: CALCO Young Researchers Workshop * * August 20, 2007, Bergen, Norway * * * * * * part of * * 2nd Conference on Algebra and Coalgebra in Computer Science * * August 20-24, 2007, Bergen, Norway * * * *------------------------------------------------------------------* * Abstract submission: April 10, 2007 * * Author notification: April 30, 2007 * * Final abstract due: May 16, 2007 * * Full paper submission: September 30, 2007 * *------------------------------------------------------------------* * http://www.ii.uib.no/calco07/ * *------------------------------------------------------------------* CALCO 2007 will be preceded by the CALCO Young Researchers Workshop, CALCO-jnr, dedicated to presentations by PhD students and young researchers at the beginning of their carriers. CALCO brings together researchers and practitioners to exchange new results related to foundational aspects and both traditional and emerging uses of algebras and coalgebras in computer science. The study of algebra and coalgebra relates to the data, process and structural aspects of software systems. This is a high-level, bi-annual conference formed by joining the forces and reputations of CMCS (the International Workshop on Coalgebraic Methods in Computer Science), and WADT (the Workshop on Algebraic Development Techniques). The first, and very successful, CALCO conference took place 2005 in Swansea, Wales. The second event will take place 2007 in Bergen, Norway. The CALCO Young Researchers Workshop, CALCO-jnr, is a CALCO satellite workshop dedicated to presentations by PhD students and by those who have completed their doctoral studies within the past few years. Attendance at the workshop is open to all - it is anticipated that many CALCO conference participants will want to attend the CALCO-jnr workshop (and vice versa). CALCO-jnr presentations will be selected according to originality, significance, and general interest, on the basis of submitted 2-page abstracts, by the organisers. A booklet with the abstracts of the accepted presentations will be available at the workshop. After the workshop, the author(s) of each presentation will be invited to submit a full 10-15 page paper on the same topic. They will also be asked to write (anonymous) reviews of papers submitted by other authors on related topics. Additional reviewing and the final selection of papers will be carried out by the CALCO-jnr PC. The volume of selected papers from the workshop will be published as a Department of informatics, University of Bergen, technical report, and it will also be made available in an open access database searchable from http://oaister.umdl.umich.edu/o/oaister/. Authors will retain copyright, and are also encouraged to disseminate the results reported at CALCO-jnr by subsequent publication elsewhere. Topics of Interest ------------------ The CALCO Young Researchers Workshop will invite submissions on the same topics as the CALCO conference: reporting results of theoretical work on the mathematics of algebras and coalgebras, the way these results can support methods and techniques for software development, as well as experience with the transition of resulting technologies into industrial practise. In particular, the workshop will encourage submissions included or related to the topics listed below. * Abstract models and logics - Automata and languages, - Categorical semantics, - Modal logics, - Relational systems, - Graph transformation, - Term rewriting, - Adhesive categories * Specialised models and calculi - Hybrid, probabilistic, and timed systems, - Calculi and models of concurrent, distributed, mobile, and context-aware computing, - General systems theory and computational models (chemical, biological, etc) * Algebraic and coalgebraic semantics - Abstract data types, - Inductive and coinductive methods, - Re-engineering techniques (program transformation), - Semantics of conceptual modelling methods and techniques, - Semantics of programming languages * System specification and verification - Algebraic and coalgebraic specification, - Formal testing and quality assurance, - Validation and verification, - Generative programming and model-driven development, - Models, correctness and (re)configuration of hardware/middleware/architectures, - Process algebra Submission ---------- Submission is by e-mail to calco-jnr(a)ii.uib.no Important Dates (all dates in 2007) ----------------------------------- 10 April Firm deadline for 2-page abstract submission 30 April Notification of abstract selection decision 16 May Final version of abstract due Early registration ends 20 August CALCO Young Researchers Workshop 21-24 August CALCO conference technical program 30 September Firm deadline for 10-15 page paper submission 15 November Notification of paper selection decision 30 November Final version of paper due Program Committee ----------------- * Magne Haveraaen, University of Bergen, Norway http://www.ii.uib.no/~magne/ * John Power, University of Edinburgh, UK http://www.inf.ed.ac.uk/people/staff/John_Power.html * Monika Seisenberger, University of Wales Swansea, UK http://www.cs.swan.ac.uk/~csmona/ -- http://www.ii.uib.no/calco07/

1 0

Thesis Fellowship in Theoretical Computer Science
by Francois Lamarche 22 Mar '07

22 Mar '07

THESIS FELLOWSHIP IN COMPUTER SCIENCE A three-year fellowship is available for a thesis in Computer Science, to be done in Nancy, in the east fo France, under the supervision of Francois Lamarche http://www.loria.fr/~lamarche SEMANTICS OF PROOFS IN CLASSICAL LOGIC During the last 2-3 years great progress has been made in our understanding of the semantics of proofs in classical logic [1][2][3], but there is still a lot to be done. The general theme of this this thesis project is the exploitation of the fruitful interaction between denotational semantics and syntax, an direction of research which began with the work of Dana Scott on the untyped lambda calculus, and has seen the invention of linear logic through Girard's observation of the category of coherence spaces and linear maps. The primary aim is to - first develop and write up a simple interpretation of classical logic in a category of posets, which is an unpublished byproduct of the denotational semantics given in [2], - then apply some of the insights given by that semantics to new approaches to proof nets for classical logic. Thus there is already some amount of material which simply has to be written up as a springboard, and should help the student pick up momentum before doing truly original research (we hasten to mention that a full mastery of the rather formidable [2] is not necessary at first for doing so). But the real interest of a thesis is to give students the occasion to prove their mettle, and we foresee plenty of openings here for doing that, with several open questions on correctness criteria, complexity, proof search, etc. In particular there is the tantalizing possibility of using non-commutative logics (that use braidings) to give a practical solution to the difficult problem of counting the number of axiom links that are used in a classical proof, which has connections to deep problems in complexity theory. Work and study environment The student would be registered at the Computer Science department one of the universities (or engineering school) which belong to the joint graduate studies program of the IAEM doctoral school. A sizeable proportion of the students registered in that school come from outside of France and Europe. Students are required to follow a moderate number of graduate courses, which are usually given in French. There are special programs aimed specifically atforeign graduate students, to help them learn French. Work will be done at the Loria laboratory of computer science http://www.loria.fr in Nancy, on the science campus. The student will be part of the Calligramme research project at INRIA-Lorraine. The student will be able to interact with everal research projects dealing with theoretical issues in computer science. The fellowship guarantees financing for three years; the student who does not complete the thesis work in that time span will be able to extend his/her stay through teaching contracts; but theses that last more than four years are exceptional and not encouraged by the authorities. Profile sought The candidate is required to have a Master's degree in Mathematics or Computer Science, with an orientation towards theoretical computer science. More precisely we expect experience in one or several of the the following topics: linear logic, the theory of {interaction, proof} nets, category theory, denotational semantics. An acquaintance with basics of deep inference is also a big plus. Procedure Putative candidates are requested to send an email to François Lamarche for further enquiry (look at http://www.loria.fr/~lamarche for exact email address and http://www.loria.fr/~lamarche/TheseEnglish.html for the html version of this announcement.) [1] C. Fuhrmann and D. Pym: Order-enriched categorical models of the classical sequent calculus. *J. Pure and App. Algebra 204(1)*. [2] F. Lamarche: Exploring the gap between linear and classical logic. *Accepted for publication in Theory and Applications of Categories*. [3] F. Lamarche and L. Strassburger: Naming proofs in classical logic, *TLCA 2005, in SLNCS 3461*

1 0

functions and polynomials
by Paul Taylor 21 Mar '07

21 Mar '07

How widely applicable is the following idea? Let f: Z x Z -> Z be a binary FUNCTION (in the sense of sets) on the integers, with the property that - for each x:Z, f(x,-) : Z -> Z is a (agrees with a unique) POLYNOMIAL, whose coefficients are functions of x; and similarly - for each y:Z, f(-,y) : Z -> Z is also a polynomial. Then f(x,y) was itself a polynomial in two variables. This generalises to a disjoint union of sets of variables, ie to functions Z^X x Z^Y -> Z that are polynomials in one set of variables for each value of the other, and vice versa. The (possible) categorical generalisation is this: Let T be a strong monad on a topos, CCC or even a symmetric monoidal closed category, and K=T0 its free algebra. Then there is a natural transformation r_X: T X ---> K^(K^X), which we suppose to be mono. (How widely is this the case?) Then the above result states that (in that case) the square (K^Y) T (X + Y) >---------> TX V | V | | | | ----- | K^Y | | r_X | K^X | V r_Y V (K^X) >--------> (K^X x K^Y) TY K is a pullback (in fact, an intersection). I am primarily concerned with the case where T encodes the theory of frames over either Set or Dcpo, though if the result extends to commutative rings or other algebraic theories, that would be very interesting too. Paul Taylor

1 0

Out of Line
by Ronnie Brown 18 Mar '07

18 Mar '07

My old popularisation paper (1993) `Out of line' has now been made into a web version by Marcus Brown, and is available from http://www.bangor.ac.uk/~mas010/outofline/out-home.html as pdf and html. I'll also mention math.AT/0702677 A new higher homotopy groupoid: the fundamental globular omega-groupoid of a filtered space which in a sense fills a gap in the construction of such higher homotopy groupoids, where the classical crossed complex, the cubical case, and the simplicial case had already been done by 1978. Ronnie Brown School of Computer Science, University of Wales, Bangor, Gwynedd LL57 1UT

1 1

CiE 2007 - Call for informal presentations
by S B Cooper 17 Mar '07

17 Mar '07

************************************************************ CiE'07: COMPUTABILITY IN EUROPE 2007 http://www.mat.unisi.it/newsito/cie07.html University of Siena Siena, 18 - 23 June 2007 CALL FOR INFORMAL PRESENTATIONS DEADLINE: 27 April, 2007 * THERE IS A REMARKABLE DIFFERENCE in conference style between computer science and mathematics conferences. Mathematics conferences allow for informal presentations that are prepared very shortly before the conference and inform the participants about current research and work in progress. The format of computer science conferences with pre-produced proceedings volumes is not able to accommodate this form of scientific communication. Continuing the tradition established at CiE 2005 in Amsterdam, and at CiE 2006 in Swansea, the 2007 conference in Siena endeavours to get the best of both worlds. * IN ADDITION TO THIS YEAR'S RECORD NUMBER of formal presentations based on our projected LNCS and local proceedings volumes, we invite researchers to present informal presentations. For this, please send us a brief description of your talk (up to and approaching one page in length) before 27 April 2007. * PLEASE SUBMIT YOUR ABSTRACT via the online Submission Form at: http://www.amsta.leeds.ac.uk/~pmt6sbc/cie07.ipform.html * If you submit an informal presentation, you will get an e-mail with a decision on acceptance or rejection within two weeks of your submission. * Let us add that there will be four post-conference special issues of journals for CiE 2007. See: http://www.amsta.leeds.ac.uk/~pmt6sbc/cie07.jour.html * All speakers, including the speakers of informal presentations, are eligible to be invited to submit a full journal version of their talk to one of the post-conference publications. PLENARY AND TUTORIAL SPEAKERS: Pieter Adriaans (Amsterdam) Yaakov Benenson (Harvard) Anne Condon (Vancouver) Stephen Cook (Toronto) Yuri Ershov (Novosibirsk) Wolfgang Maass (Graz) Sophie Laplante (Paris) Anil Nerode (Cornell) George Odifreddi (Turin) Roger Penrose (Oxford) Michael Rathjen (Leeds) Dana Scott (Carnegie Mellon) Robert I. Soare (Chicago) Philip Welch (Bristol) SPECIAL SESSIONS SPEAKERS: Eric Allender (Rutgers) Andrej Bauer (Ljubljana) Vasco Brattka (Cape Town) Douglas Bridges (Canterbury, NZ) John Case (Newark, Delaware) Pieter Collins (Amsterdam) Thierry Coquand (Goeteborg) Felix Costa (Lisbon) Barbara F. Csima (Waterloo) Abbas Edalat (London) Martin Escardo (Birmingham) Joerg Flum (Freiburg) Sergey S. Goncharov (Novosibirsk) Hajime Ishihara (Tokyo) Natasha Jonoska (Tampa, Florida) Michal Koucky (Prague) James Ladyman (Bristol) Maria Emilia Maietti (Padua) Giancarlo Mauri (Milan) Klaus Meer (Odense) Itamar Pitowsky (Jerusalem) Robert Rettinger (Hagen) Grzegorz Rozenberg (Leiden) Frank Stephan (Singapore) Neil Thapen (Prague) Giuseppe Trautteur (Naples) Heribert Vollmer (Hannover) Osamu Watanabe (Tokyo) Jiri Wiedermann (Prague) Damien Woods (Cork) Liang Yu (Nanjing) Martin Ziegler (Paderborn) WOMEN IN COMPUTABILITY WORKSHOP in association with the Computer Research Association's Committee on the Status of Women in Computing Research (CRA-W) Organisers: Paola Bonizzoni, Elvira Mayordomo. Speakers: Anne Condon (Vancouver), Natasha Jonoska (Florida), Carmen Leccardi (Milan), and others CONFIRMED SPONSORS OF CiE 2007: AILA (Associazione Italiana di Logica e Applicazioni), EATCS (European Association for Theoretical Computer Science), ASL (Association for Symbolic Logic), EACSL (European Association for Computer Science Logic), FoLLI (The Association of Logic, Language and Information), GNSAGA-INdAM (Gruppo Nazionale per le Strutture Algebriche e Geometriche e loro Applicazioni-Istituto NAzionale di Alta Matematica) and The University of Siena. * CiE 2007 will be co-located with CCA 2007, the annual CCA (Computability and Complexity in Analysis) Conference: http://cca-net.de/cca2007/ ************************************************************

1 0