On building trees with minimum height, relationally

S-C. Mu and R. S. Bird. In First Asian Workshop on Programming Languages and Systems, Singapore, December 2000.
[GZipped Postscript]

The algebraic style of reasoning about programs has been proposed and studied by computing scientists. We rephrase the old problem of building trees of minimum height as an optimisation problem and apply the greedy theorem to derive a linear time algorithm. To put the problem in the right form, we find it necessary to generalise from functions to relations and make use of the converse of a function theorem to write the inverse of a function as a fold.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>