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
23-Jan-2002 08:45:04 -0400,5395;000000000000-00000000