most recent 30 from http://mathoverflow.net 2013-05-19T17:09:18Z http://mathoverflow.net/feeds/user/21638 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89086/examples-of-algorithms-that-came-from-category-theory/89227#89227 Ross Tate 2012-02-22T20:42:13Z 2012-02-22T20:42:13Z

<p>I'm glad you liked the paper. I thought you might like to know that the algorithms for both of my PLDI papers were actually designed using a category-theoretic framework I made for existential types (half of which turned out to be opfibrations, but I didn't know about those at the time). Others have asked to see it, so I'm finally giving in and posting the work-in-progress on my page for <a href="http://cseweb.ucsd.edu/~rtate/publications/italx/" rel="nofollow">Inferable Object-Oriented Typed Assembly Language</a>, since that's the problem which prompted me to make the framework once I get stuck. Just look for "Inferable Existential Quantification". Hope you like it!</p> <p>One thing I'll note while I'm at it is that, in my experience, "algorithmic" category theory (as opposed to "type-theoretic" and "semantic" category theory) is largely built on concrete category theory. After all, many algorithms deal with structured sets of some form. Thus the techniques available to an algorithm often depend on whether the concrete category is topological or algebraic rather than whether it is closed. There's lots of stuff showing what kind of structurings preserve things like existence of pushouts and pullbacks, but I think it would be really interesting (and helpful) to also identify what kind of structurings preserve constructability/decidability of pushouts and pullbacks. By knowing that, we could build algorithms for a domain just by showing how the domain can be built from a sequence of constructability-preserving structurings that consequently guarantee the presence of the particular structures required by the algorithm. If anyone happens to already know of such research, I'd be very interested to see it.</p>