Date: Fri, 19 Oct 2012 07:18:05 +0100 (BST) From: Jocelyn Ireson-Paine <popx@j-paine.org> To: categories <categories@mta.ca> Subject: Re: Algorithms arising from category theory In-Reply-To: <alpine.LRH.2.02.1210170704400.10360@sphinx.mythic-beasts.com> References: <alpine.LRH.2.02.1210170704400.10360@sphinx.mythic-beasts.com> 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/ ]