categories: Re: Kan extensions

["Ronald Brown" <Ronnie.Brown@tesco.net>]

reply to r.brown@bangor.ac.uk

Robert

There is a paper

R. Brown and  Anne Heyworth, `Using rewriting systems to compute
left Kan extensions and induced actions of categories', J.
Symbolic Computation 29 (2000) 5-31.

which does not answer your question on power but instead shows that the
Knuth-Bendix process for computing complete rewrite systems for
presentations of monoids  can be extended to  `presentations of Kan
extensions'.  The method seems different from that of Carmody-Walters, but
was inspired by it. See Anne's home page at Leicester for more papers in
this area. The `power' of the K-B method is improved since it applies to
more examples.

Ronnie Brown

----- Original Message -----
From: "Robert Byrne" <rbyrne3@cs.tcd.ie>
To: <categories@mta.ca>
Sent: Monday, January 21, 2002 12:58 PM
Subject: categories: Kan extensions


> Dear Category Theory list,
>
> I would like to know if anyone has any references regarding the use of the
> computation of Kan extensions as a model of computation (e.g. how powerful
> is some given algorithm as compared to a Turing machine). I have seen the
> Walters-Carmody algorithm in 'Categories and Computer Science', but there
> is no mention there of the computational power of the algorithm presented.
>
> Any information would be welcome.
>
> Yours,
>
> --
> Robert Byrne
>
>
>
>
>