From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/7482 Path: news.gmane.org!not-for-mail From: Bob Rosebrugh Newsgroups: gmane.science.mathematics.categories Subject: BOUNCE categories@mta.ca: Approval required: (fwd) Date: Fri, 19 Oct 2012 08:40:07 -0300 (ADT) Message-ID: Reply-To: Bob Rosebrugh NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII X-Trace: ger.gmane.org 1350646838 31627 80.91.229.3 (19 Oct 2012 11:40:38 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 19 Oct 2012 11:40:38 +0000 (UTC) To: categories Original-X-From: majordomo@mlist.mta.ca Fri Oct 19 13:40:45 2012 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtpx.mta.ca ([138.73.1.134]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TPAwT-000523-NY for gsmc-categories@m.gmane.org; Fri, 19 Oct 2012 13:40:41 +0200 Original-Received: from mlist.mta.ca ([138.73.1.63]:57901) by smtpx.mta.ca with esmtp (Exim 4.77) (envelope-from ) id 1TPAux-0001Ds-UA; Fri, 19 Oct 2012 08:39:07 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1TPAvv-0004xn-9H for categories-list@mlist.mta.ca; Fri, 19 Oct 2012 08:40:07 -0300 User-Agent: Alpine 2.02 (LRH 1266 2009-07-14) Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:7482 Archived-At: Date: Fri, 19 Oct 2012 07:18:05 +0100 (BST) From: Jocelyn Ireson-Paine To: categories Subject: Re: Algorithms arising from category theory In-Reply-To: References: User-Agent: Alpine 2.02 (LRH 1266 2009-07-14) MIME-Version: 1.0 Content-Type: MULTIPART/MIXED; BOUNDARY="1566387330-216115030-1350627485=:16362" This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. --1566387330-216115030-1350627485=:16362 Content-Type: TEXT/PLAIN; format=flowed; charset=ISO-8859-15 Content-Transfer-Encoding: QUOTED-PRINTABLE [Note from moderator: some list members received this post without its text so it is being resent.] On Mon, 15 Oct 2012, Mike Stay wrote: > I'd like to get more computer programmers interested in category > theory. >=20 Yes! > There's the obvious connection to type theory and categorical > semantics, but programmers are usually far more interested in > algorithms. > ... > Can any readers point me to other algorithms that were discovered by > turning to category theory or to reports of problems solved by > realizing they were instances of an abstraction of another solved > problem? >=20 In http://tinyurl.com/98ydhkh , "Computational Category Theory", David=20 Rydeheard and Rod Burstall derive an algorithm for unifying terms (in the= =20 sense used in logic programming), treating it as the construction of=20 coequalisers. (Their original paper, "A Categorical Unification=20 Algorithm", is on the Web, but I can only find copies that are locked up=20 behind a Springer paywall.) There are more recent such algorithms, e.g.=20 http://tinyurl.com/9rqltv6 , "A categorical approach to unification of=20 generalised terms" by Eklund, Gal=E1n, Medina, Ojeda-Aciego and Valverde. My "Excelsior" spreadsheet-modularisation software, described in=20 http://www.j-paine.org/calco2011/paper.html , "Module Expressions for=20 Modularising Spreadsheets and Sharing Code between Them", was inspired by= =20 category theory, specifically by Joseph Goguen's sheaf semantics for=20 interacting objects. Goguen has used colimits and 3/2-colimits to model conceptual blending and = the=20 interpretation of metaphors: http://cseweb.ucsd.edu/~goguen/pps/taspm.pdf ,= =20 "Mathematical Models of Cognitive Space and Time". Michael Healy has used natural transformations and functors as a guide to= =20 combining neural networks:=20 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.32.2635 , "Catego= ry=20 Theory Applied to Neural Modeling and Graphical Representations". Michael Healy, Thomas Caudell, and Timothy Goldsmith have proposed that=20 compound concepts could be represented as categorical diagrams, and that=20 concepts could be compared by comparing these diagrams. They say that for s= ome=20 simple test examples, the results of these comparisons are fairly close to= =20 human performance, and that this is therefore worth considering as a=20 mathematical model of human concept representation and comparison:=20 http://repository.unm.edu/handle/1928/6724 , "A Model of Human Categorizati= on=20 and Similarity Based Upon Category Theory". Ronnie Brown and Tim Porter suggest that higher-dimensional algebra and=20 colimits might be useful for sensoty integration, though they don't develop= any=20 algorithms: http://arxiv.org/PS_cache/math/pdf/0306/0306223v1.pdf , "Category Theory an= d=20 Higher Dimensional Algebra: potential descriptive tools in neuroscience". Manfred Liebmann has used multicategories and operads as a guide to designi= ng=20 parallel numerical algorithms:=20 http://paralleltoolbox.sourceforge.net/categorytheory.pdf , "Category Theor= y=20 and the Design of Parallel Numerical Algorithms". There has been a lot of work on merging ontologies by using categorical=20 constructions, usually pushout and colimit. See e.g. Pascal Hitzler, Markus= =20 Kr=F6tzsch, Marc Ehrig, York Sure in=20 http://knoesis.cs.wright.edu/faculty/pascal/resources/publications/cando05.= pdf,=20 "What Is Ontology Merging? - A Category-Theoretical Perspective Using Pusho= uts"=20 and Google "combining ontologies categorically". I once suggested that, via algebraic-specification languages such as CafeOB= J,=20 category theory could be used to guide the construction and modularisation = of=20 large Web sites: http://www.j-paine.org/alg_web_spec.html , "Algebraic Web= =20 specification". There's quite a lot of other stuff out there. I hope these examples fit the spirit of Mike's question. Quite often, it se= ems=20 that the authors use category theory as a guide, searching it for construct= ions=20 that they might instantiate as data structures. They then devise algorithms= to=20 build these structures. Usually, they do so informally, rather than by form= ally=20 deriving the algorithm from a categorical definition. Very often, the=20 categorical construction they use is a pushout or colimit. That's the=20 impression I have, anyway. So what they're doing is along the lines suggest= ed=20 by Goguen in his "A Categorical Manifesto",=20 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.13.362 . By the way, in=20 http://www.j-paine.org/dobbs/why_be_interested_in_categories.html , "What M= ight=20 Category Theory do for Artificial Intelligence and Cognitive Science?", I= =20 suggest that these two fields are ripe for the plundering of apparently=20 unrelated concepts that category theory might be able to unify. > Mike Stay - metaweta@gmail.com > http://www.cs.auckland.ac.nz/~mike > http://reperiendi.wordpress.com >=20 Jocelyn Ireson-Paine http://www.j-paine.org/index.html Jocelyn's Cartoons http://www.j-paine.org/blog/jocelyns_cartoons/ --1566387330-216115030-1350627485=:16362-- [For admin and other information see: http://www.mta.ca/~cat-dist/ ]