Patent ID: 7882459

Claim:
A computer-readable medium having a computer program product for reducing subexpressions in structural design representations, said computer-readable medium comprising: instructions for receiving an initial design, wherein said initial design represents an electronic circuit containing an AND gate; instructions for selecting a first simplification mode for said initial design from a set of applicable simplification modes, wherein said first simplification mode is an AND/OR simplification mode; instructions for performing a simplification of said initial design according to said first simplification mode to generate a reduced design; instructions for determining whether a size of said reduced design is less than a size of said initial design, and for replacing said initial design with said reduced design in response to a determination that said size of said reduced design is less than said size of said initial design; instructions for identifying a minimal set of one or more roots, wherein said one or more roots represent one or more functions requiring preservation; instructions for enqueueing in one or more root queues one or more leaves of each of said one or more roots; instructions for using a set of rewriting rules to simplify said one or more root queues; instructions for, for each one or more roots in said one or more root queues, replacing one or more common leaves in said root queue of a first gate with a second gate, wherein said first gate is a superset of said second gate; instructions for clustering said one or more roots into one or more leaf-disjoint groups; instructions for successively eliminating one or more common leaf sets from each of said one or more root queues; instructions for creating corresponding gates over said common leaf sets; instructions for replacing common leaves in said root queues with new gates, thus resulting in adding said new gates to said root queues; and instructions for building one or more depth-balanced trees for each root.