October 2002 - Categories - categories.org.au

MFPS Deadline extended
by Michael Mislove 01 Nov '02

01 Nov '02

Dear Colleagues, The deadline for submissions to the Nineteenth Conference on the Mathematical Foundations of Programming Semantics (MFPS XIX) has been extended. The deadline is now midnight, Pacific standard time, Friday, November 8, 2002. The URL for submissions is http://mfpssubm.CS.McGill.CA/ Details about the meeting also can be found at the URL http://www.math.tulane.edu/~mfps/mfps19.htm Best regards, Mike Mislove =============================================== Professor Michael Mislove Phone: +1 504 862-3441 Department of Mathematics FAX: +1 504 865-5063 Tulane University URL: http://www.math.tulane.edu/~mwm New Orleans, LA 70118 USA ===============================================

1 0

Category theory and data analysis
by Jean-Pierre Marquis 30 Oct '02

30 Oct '02

Someone asked me recently whether category theory might help in organizing disease data into a hierarchy of some sort. That person is familiar with data analysis and statistics but does not know any category theory. Is there any literature that can be recommended which might be helpful? Thank you, Jean-Pierre Marquis 31-Oct-2002 16:59:52 -0400,1462;000000000001-00000000

1 0

Re: quotient (co)classifier?
by Vaughan Pratt 25 Oct '02

25 Oct '02

From: "Al Vilcius" <al.r(a)vilcius.com> >We have a beautiful notion of subobject classifier true:1-->omega >Is there a similar (ie. dual) notion of quotient (co)classifier? >- perhaps formulated using pushouts? This is of course what omega becomes in the opposite of any topos. While the duality principle for ordinary categories makes any separate treatment of the dual case redundant, this is not so clear for practical applications. Has this in fact happened: has anyone gotten any useful mileage out of abstracting CABA to dual toposes as the dual of abstracting Set to toposes, e.g. applications to or generalizations of Boolean-based logics? One imagines that, just as natural numbers inhabit the natural number object of a topos T, propositions would inhabit the proposition objects of a dual topos T\op, defined simply as the power objects Omega^X in T, where arbitrary object X of T takes on the role of propositional variables object. ("Proposition object" here is intended as the topos-theoretic counterpart of free Boolean algebra, or rather free CABA.) Or is there a better notion of proposition object for a dual topos? What does "cotopos" mean for V.L. Vasyukov, as in his "Developing Tarski: a cotopos of theories" (Logical Investigations. Vol 3, Moscow, 1995.)? Vaughan Pratt 25-Oct-2002 14:53:17 -0300,7162;000000000000-00000000

2 1

quotient (co)classifier?
by Al Vilcius 25 Oct '02

25 Oct '02

We have a beautiful notion of subobject classifier true:1-->omega Is there a similar (ie. dual) notion of quotient (co)classifier? - perhaps formulated using pushouts? 24-Oct-2002 21:07:53 -0300,2136;000000000000-00000000

2 1

LICS 2003 CFP
by Alex Simpson 24 Oct '02

24 Oct '02

LICS 2003 CALL FOR PAPERS Eighteenth Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE June 22nd -- 25th, 2003, Ottawa, Canada http://www.lfcs.informatics.ed.ac.uk/lics/ The LICS Symposium is an annual international forum on theoretical and practical topics in computer science that relate to logic in a broad sense. We invite submissions on that theme. Suggested, but not exclusive, topics of interest for submissions include: automata theory, automated deduction, categorical models and logics, concurrency and distributed computation, constraint programming, constructive mathematics, database theory, domain theory, finite model theory, formal aspects of program analysis, formal methods, hybrid systems, lambda and combinatory calculi, linear logic, logical aspects of computational complexity, logics in artificial intelligence, logics of programs, logic programming, modal and temporal logics, model checking, programming language semantics, reasoning about security, rewriting, specifications, type systems and type theory, and verification. IMPORTANT DATES: To expedite the assignment of papers to reviewers, this year authors are required to submit electronically a paper title and a short abstract of about 100 words before submitting the extended abstract of the paper. Titles & Short Abstracts Due: December 30, 2002 Extended Abstracts Due: January 6, 2003 Author Notification: March 18, 2003 Camera-ready Papers Due: April 11, 2003. All deadlines are firm; late submissions will not be considered. Detailed information about electronic paper submission will be posted at the LICS website. SUBMISSION INSTRUCTIONS: This year every extended abstract must be submitted electronically in the IEEE Proceedings two-column camera-ready format. It must be in English and provide sufficient detail to allow the program committee to assess the merits of the paper. It should begin with a succinct statement of the issues, a summary of the main results, and a brief explanation of their significance and relevance to the conference and to computer science, all phrased for the non-specialist. Technical development directed to the specialist should follow. References and comparisons with related work should be included. Extended abstracts may be no longer than 10 pages including references, and must be formatted in the IEEE Proceedings two-column camera-ready style (IEEE style files are accessible from the LICS website). If necessary, detailed proofs of technical results can be included in a clearly-labelled appendix in the same two-column format following the 10-page extended abstract or there can be a pointer to a manuscript on a web site. This material may be read at the discretion of the program committee. Extended abstracts not conforming to the above requirements concerning format and length will be rejected without further consideration. The results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. The PC chair should be informed of closely related work submitted to a conference or journal between January 6th, 2003 and March 18th, 2003. All authors of accepted papers will be expected to sign copyright release forms. One author of each accepted paper will be expected to present it at the conference. SHORT PRESENTATIONS: LICS 2003 will have a session of short (5--10 minutes) presentations. This session is intended for descriptions of work in progress, student projects, and relevant research being published elsewhere; other brief communications may be acceptable. Submissions for these presentations, in the form of short abstracts (1 or 2 pages long), should be entered at the LICS 2003 submission site between March 17th and March 21st, 2003. Authors will be notified of acceptance or rejection by April 4th, 2003. KLEENE AWARD FOR BEST STUDENT PAPER: An award in honor of the late S.C. Kleene will be given for the best student paper, as judged by the program committee. Details concerning eligibility criteria and procedure for consideration for this award will be posted at the LICS website. The program committee may decline to make the award or may split it among several papers. INVITED SPEAKERS: LICS 2003 will feature invited talks by Erich Graedel (RWTH Aachen), John Harrison (Intel Corp.), Marta Kwiatkowska (U. Birmingham), John McCarthy (Stanford U.), and invited tutorials by Martin Abadi (UC Santa Cruz) and Benjamin Pierce (U. Pennsylvania). AFFILIATED WORKSHOPS: As in previous years, there will be a number of workshops affiliated with LICS 2003; information will be posted at the LICS website. SPONSORSHIP: The symposium is sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with the Association for Symbolic Logic, and the European Association for Theoretical Computer Science. PROGRAM CHAIR: Phokion G. Kolaitis Computer Science Department University of California, Santa Cruz Santa Cruz, CA 95064, USA Email:kolaitis@cs.ucsc.edu Phone: + 1 831 459 4768, Fax: + 1 831 459 4829 PROGRAM COMMITTEE: Michael Benedikt, Andreas R. Blass, Maria Luisa Bonet, Witold Charatonik, Marcelo Fiore, Giorgio Ghelli, Thomas A. Henzinger, Alan Jeffrey, Assaf J. Kfoury, Phokion G. Kolaitis, Orna Kupferman, Ursula Martin, Paul-Andre Mellies, Eugenio Moggi, Ugo Montanari, Paliath Narendran, Luke Ong, Martin Otto, Frank Pfenning, Mirek Truszczynski. CONFERENCE CO-CHAIRS: Amy Felty & Philip Scott SITE Math. and Stat. University of Ottawa Ottawa, Ontario, K1N 6N5, Canada Email: {afelty,phil(a)site.uottawa.ca} WORKSHOPS CHAIR: Prakash Panangaden, McGill U., prakash(a)cs.mcgill.ca PUBLICITY CHAIR: Alex Simpson, U. of Edinburgh, Alex.Simpson(a)ed.ac.uk GENERAL CHAIR: Samson Abramsky, U. of Oxford, Samson.Abramsky(a)comlab.ox.ac.uk ORGANIZING COMMITTEE: M. Abadi, S. Abramsky (chair), A. Aggarwal, M. Bezem, E. Clarke, R. Constable, N. Dershowitz, J. Diaz, H. Ganzinger, F. Giunchiglia, M. Grohe, J. Halpern, U. Kohlenbach, D. Leivant, L. Libkin, G. Longo, D.A. Martin, H. Mairson, J. Mitchell, E. Moggi, G. Plotkin, V. Pratt, J. Riecke, S. Ronchi della Rocca, J. Tiuryn, M.Y. Vardi, J. Vitter, G.Winskel. ADVISORY BOARD: M.Abadi, S. Abiteboul, M. Dezani, J. Halpern, R. Impagliazzo, D. Kozen, L. Pacholski, A. Scedrov, D. Scott, J. Wing. 25-Oct-2002 14:53:52 -0300,4296;000000000000-00000000

1 0

formal languages and monads
by J=FCrgen Koslowski 21 Oct '02

21 Oct '02

Hello, The following question on sci.math.research didn't get much response, except from M.W. Hopkins himself. Maybe some category theorists can comment on this? (The question was aimed at a general math audience.) =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D M.W. Hopkins' algebraic approach to formal languages http://www.uwm.edu/~whopkins/cs/CompFAQ.txt seems to be based on the following observations: The free monoid construction, so fundamental in formal language theory, is of course part of a monad, with the inclusion of letters as singleton words as unit and the concatenation of strings of words as multplication. Similarly, we have the (covariant) powerset monad with the singleton map as unit and the union operation as multiplication. Its Eilenberg-Moore algebras are just SUP-semilattices (having arbitrary suprema). These monads are linked by a distributive law in the sense of Beck (69): \delta_X : (PX)^* --> P(X^*) maps a string of subsets to the set of words where the i-th letter belongs to the i-th subset. The resulting composite monad has unital quantales a EM-algebras. Moreover, the powerset monad on set lifts to a powerset monad on mon (the category of EM-algebras of the free monoid monad), again with unital quantales as EM-algebras. Passing from powersets PX to sets of finite subsets FX, the distributive law \delta restricts accordingly. The finite powerset monad over set has sup-semilattices as EM-algebras (finite suprema), while its lift to mon has so-called "dioids" as EM-algebras. Now formal language theory *should* be concerned with studying "interesting" submonads - either of the composite of the free monoid monad and the powerset monad over set, - or of the lifted powerset monad over mon. These submonads in turn should "contain" - the composite of the free monoid monad with the sup-semilattice monad over set, respectively - the dioid-monad over mon. "Interesting" submonads would be those which admit a Kleene star operation (which the latter two do not). The least submonad which does just gives rise to regular languages/subset; its EM-Algebras being the Kleene algebras. Is anybody besides M.W. Hopkins actually viewing formal language theory from this angle? This approach stikes me as much cleaner and simpler than what is usually presented in textbooks, but also in the Handbook of Formal Languages. I wouldn't be surprised if this was known to category theorists in the 60's or 70's, but never found its way to the computer scientists (no flame wars, please). =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D While none of this is particularly deep, I find it a very pretty applicatio= n of category theory, one that might win over some computer scientists. -- Juergen --=20 Juergen Koslowski If I don't see you no more on this world ITI, TU Braunschweig I'll meet you on the next one koslowj(a)iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR) 24-Oct-2002 15:37:24 -0300,895;000000000000-00000000

1 0

FICS 03
by =C9sik Zolt=E1n 21 Oct '02

21 Oct '02

Fixed Points in Computer Science FICS'03 A Satellite Workshop to ETAPS'2003 12-13 April, 2003, Warsaw, Poland CALL FOR PAPERS Aim. 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 such as: design and implementation of programming languages, program logics, databases. 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 theory of fixed points. Previous workshops where held in Brno (1998, MFCS workshop), Paris (2000, LC2000 workshop), Florence (2001, PLI workshop). Copenhagen (2002, LICS workshop). Topics include, but are not restricted to: Construction and reasoning about properties of fixed points, categorical, metric and ordered fixed point models, continuous algebras, relation algebras, regular algebras of finitary and infinitary languages, formal power series, word and tree automata, the mu-calculus and other programming logics, fixed points in process algebras and process calculi, fixed points and the lambda calculus, fixed points in relation to dataflow and circuits, fixed points in logic programming, databases and complexity theory. Programme Committee: J. Adamek (Braunschweig) R. Amadio (Marseille) R. Backhouse (Nottingham) S. Bloom (Hoboken NJ) J. Bradfield (Edinburgh) A. Dawar (Cambridge) R. De Nicola (Florence) Z. Esik (cochair, Szeged) I. Guessarian (Paris) M. Mislove (Tulane) I. Walukiewicz (cochair, Bordeaux) Invited speakers: Martin Grohe (Edinburgh) Erich Gradel (Aachen) Damian Niwinski (Warsaw) Leszek Pacholski (Wroclaw) Contact person: Igor Walukiewicz LaBRI Domaine Universitaire, bat. A30 351, cours de la Liberation 33405 Talence Cedex FRANCE igw(a)labri.fr phone: +33 5 56.84.69.00 fax: +33 5 56.84.66.69 Paper submission: Authors are invited to send three copies of an abstract not exceeding three pages to Igor Walukiewicz. Electronic submissions in the form of uuencoded postscript files are encouraged and can be sent to igw(a)labri.fr. Submissions are to be received before February 14, 2003. Authors will be notified of acceptance by March 10, 2003. Proceedings: Preliminary proceedings containing the abstracts of the talks will be available at the meeting. Final proceedings will be published after the meeting as a special issue of Theoretical Informatics and Application (http://www.edpsciences.org/docinfos/ITA/) The meeting will be organized in affiliation to ETAPS'03: http://www.mimuw.edu.pl/etaps03 Important Dates: Submission: February 14, 2003 Notification: March 10, 2003 Final version of the abstract: \March 17, 2003 More information is available at the web site http://www.labri.fr/~igw/fics -- Zoltan Esik Professor Tel: 36-62-544-289 Dept. of Computer Science Fax: 36-62-544-895 University of Szeged email: esik(a)inf.u-szeged.hu 6720 Szeged, P.O.B. 652 http://www.inf.u-szeged.hu/~esik Hungary 21-Oct-2002 22:22:42 -0300,6382;000000000001-00000000

1 0

Re: subobects and mereology?
by Alberto Peruzzi 21 Oct '02

21 Oct '02

To Bill Halchin's question on mereology: Mereology is a subject which traces back to Husserl's Logical Investigations (1900). As a formalized theory, it was developed mainly by the Polish logician and philosopher C. Lesniewski. As for a critical comparison between mereology and category theory, let me remind that, since mereology is no less based on the unanalized notion of sets, common theories of mereology are defective: insofar as semantic entities are the correlate of conceptual constructions, they are not to be viewed as sets, be they punctate or pointless. This remark would itself be pointless, were mereology intended as a theory of parts and wholes independent of the phenomenological aspects of semantics. But then its interest as a ³formal ontology² would be reduced, and lack of consideration for the process aspects (the ³maps²) would mean it served to describe only a static world. As for the relationships between mereology and topology : simple constructions such as the quotient space, the compactification, the connected sum of manifolds, etc., should serve as a reminder that topology is more than a taxonomy of different kinds of spaces (or different regions in space). It is also a theory of how different kinds of continuous variation affect the properties of any given space (and its regions) and how these kinds of variation are algebraically expressible. It is precisely because of this, that topology is more relevant to applied semantics than mereology. So, rather than some weak form of topology, a richer theory has to be sought for, in which different notions of space can be compared. Mereology is also based on the idea of ³objects in general². But one can doubt the existence of ³objects in general², as intended referents of a formal ontology, independent of any material domain. True, a similar doubt can also apply to abstract sets and arbitrary categories: for this very reason it is suitable to see the foundations of semantics and the foundations of mathematics as intimately linked. Typing is relevant here, yet it does not solve the philosophical problem concerning the way any notion of object is possible, as rooted in features (not point-like but still nomological) of the ³common-sense² world. For instance, in natural language even the notion of ³set² is expressed in a typed manner, one sensitive not only to the ³homogeneity² of the entities collected, but also to the mereological modality of their grouping (team, sheaf, fleet, swarm, series, bunch, cluster, etc.). The claim is that set theory results from a (usually implicit) abstraction from the type and the modality whithin which entities are collected modalities are not simply order types. That contemporary mathematics succeds in recovering such modalities (e. g. consider the topos G-Sh(X) of sheaves over a space X, with a group G acting on them) is a fact of crucial philosophical importance. It also suggests that mathematics is directly involved with structures of the material world and does not need logic or language as intermediacy agencies though, evidently, mathematics needs language and logic in order to be communicated and organised in a stable way. A theory investigating the relationships of part and whole remains inadequate until the stability of the objects involved with respect to (actual or imagined) actions is taken into account. There have been attempts at axiomatising mereology in (classical) first order logic, but they either presuppose (classical) set theory or occur in a semantic vacuum. Phenomenological wholes are rich in structure, so they have rather to be investigated by starting with a category of G-spaces (e. g. the category of differentiable manifolds with the action of a Lie group), then passing to sheaves over such spaces. Likewise, the problem of constraining the formation of unions of parts (of a given whole) also has a direct solution: parts and their unions are different from arbitrary subsets, being closed with respect to G-action. (In order to be applied in cognitive science, such a model will have to be greatly refined, taking into account edges, junctures, etc.) Of course, the difficulty lies in dealing with singularities. Let me suggest you the reading of what I wrote on the intrinsic limits of mereology, both from a mathematical point of view and from the point of view of its use as a tool to be applied in the semantic theory of (fragments) of natural language, in the following papers: Constraints on Universals, in R. Casati, B. Smith (eds.), Philosophy and the Cognitive Sciences, Hölder-Pichler-Tempsky, Vienna 1994, pp. 357-370. Action of Structures, Structure of Actions, Axiomathes, 7 (1996), pp. 325-348. An Essay on the Notion of Schema, in L. Albertazzi (ed.), Shapes of Form, Kluwer, Amsterdam 1999, pp. 191-243. The Geometric Roots of Semantics, in L. Albertazzi (ed.) Meaning and Cognition, John Benjamins, Amsterdam, 2000, pp. 169-201. On 20-10-2002 2:29, "Galchin Vasili" <vngalchin(a)yahoo.com> wrote: > Hi Cat community, > > In Jeremy Buffterfield's paper (Section 1.3) below he says "a formal > generalization of the notion of part as studied in mereology, so as to > allow for 'structured parts'." > > http://philsci-archive.pitt.edu/documents/disk0/00/00/01/92/ > > What is meteology? (I did look on the Web but I didn't understand anything). > > Thanks and regards, Bill Halchin > Alberto Peruzzi Dipartimento di Filosofia Via Bolognese 52 50139 Firenze Italia 21-Oct-2002 22:24:25 -0300,3794;000000000000-00000000

1 0

subobects and mereology??
by Galchin Vasili 20 Oct '02

20 Oct '02

Hi Cat community, In Jeremy Buffterfield's paper (Section 1.3) below he says "a formal generalization of the notion of part as studied in mereology, so as to allow for 'structured parts'." http://philsci-archive.pitt.edu/documents/disk0/00/00/01/92/ What is meteology? (I did look on the Web but I didn't understand anything). Thanks and regards, Bill Halchin 21-Oct-2002 22:22:41 -0300,3939;000000000001-00000000

1 0

Re: semantics for F_{sub,rec} ??
by Thomas Streicher 18 Oct '02

18 Oct '02

[----- The Types Forum, http://www.cis.upenn.edu/~bcpierce/types -----] Dear Kim, thank you for the clear statement about the state of the art w.r.t. F_{omega,sub,rec}. It conforms that my understanding wasn't absolutely mistaken. I never doubted that the interesting equations can be solved this way. So I see two possibilities in case one cannot give denotational meaning to the full calculus F_{omega,sub,rec}. Either one just takes it as a metalanguage having suffiicently good operational properties (your choice) or, if one wants to work denotationally based, to consider types a subsets of or pers on some untyped universe. Thomas Streicher 20-Oct-2002 22:37:03 -0300,927;000000000000-00000000

1 0