BOUNCE categories@mta.ca: Approval required: (fwd)

[Bob Rosebrugh <rrosebru@mta.ca>]

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/ ]