On optimizing the evaluation of a set of expressions

A branch- and-bound type algorithm is developed to optimize the evaluation of a set of expressions. The algorithm proceeds in a depth-first manner and achieves an optimal solution. The algorithm is applied to optimize the evaluation of sets of relational expressions. Analogies to the heuristic information associated with theA* algorithm are investigated. Examples are presented illustrating the use of the algorithm. Pragmatics associated with the algorithm and its application to Boolean optimization are also discussed.Research supported by the National Science Foundation under grant number NSF MCS 79-19418 and by the National Aeronautics and Space Administration under grant number NGR 21-002-270-9.