This paper derives exact equations for the maximum number of nonterminal vertexes in reduced and quasi-reduced ordered binary decision diagrams (OBDD's). A reduced OBDD is reduced by both merging and deleting vertices, and a quasi-reduced OBDD is reduced only by merging. These formulas are used to tighten Lee's original bounds, and to correct the bounds recently reported by H.T. Liaw and C.S. Lin (1992).>

A fast algorithm for minimizing the two-level AND/XOR representation of combinational functions, based on a graphical data structure similar to the OBDD, is described. This GMX (Graphical Minimizer for XORs) algorithm works by 'reading-off' and minimizing the solution from an augmented OBDD, called an SFG. The advantage of the SFG structure is that it is often of polynomial size. The algorithm generates solutions significantly better, or no worse, than all previously published solutions on a set of example circuits.>

The authors introduce a new deterministic test pattern generation algorithm for sequential circuits. The Sequential Target Switching (STarS) algorithm begins generating a test sequence for a specific target fault, but as each pattern is generated, it keeps track of the set of faults that may also use this sequence as part of a test. Backtracking is avoided by switching the target fault to a member of this fault set, and partial sequences are re-used as much as possible.>