Many problems in algorithm design can be specified in two parts, one
defining a broad class of solutions (the "easy'' part) and the other
requesting one particular such solution, optimal in some sense (the
"hard'' part). This dichotomy is nicely captured by Galois connections
(GC) in which one of the adjoints delivers the optimal (hard) solution.
We show how the algebra of GCs can be used to reason about such
algorithms independently of their implementation, and introduce a binary
relational combinator whereby such implementations can be calculated
using the (relational) algebra of programming. The approach extends
results previously known for so-called "greedy'' and "dynamic''
programming in a way which makes them more systematic and easier to
apply. (joint work with Shin-Cheng Mu, Academia Sinica, Taiwan) |