Efficient Computation of Expressions with Common Subexpressions

Previous results have shown that it is easy to generate optimal code from express,on trees, and that optimal code generauon becomes very difficult ff arbitrary common subexpress,ons are handled In this paper a class of expressions containing restricted common subexpressions from which optimal code can be generated effictentty is studied. These expressions are represented by a class of series-parallel graphs, which the authors call collapsible graphs, that mchide trees and are general enough to permit large common subexpresslons, but from which optmml code can be generated m polynomml time for a class of stack machines.