Specialized Applications of Decision Diagrams

Alan Mishchenko

Abstract (Slides)

Solving problems using decision diagrams (DDs) often involves the development of specialized traversal procedures not avaiable in the standard distribution of a DD package. This talk focuses on the generic structure and principles of the traversal procedures using different DDs (BDD, ADD, ZDD, MDD). Experimental results show that these procedures are orders of magnitude faster than typical work-arounds using standard functionality of the package. This is especially true when a problem can be reduced to checking conditions on a DD, without building new DD nodes. Illustrative examples include the computation of primes and supercubes, the implicit reduction of the covering table in exact SOP minimization (introduced by O.Coudert), checking the existence of decomposition for multi-valued relations, optimal encoding of subfunctions in decomposition, and computation of the complete set of spectral coefficients without deriving the transform matrix. The illustrative examples have been implemented using CUDD package (Release 2.3.1). The source code is available on-line as part of the EXTRA library:
http://www.ee.pdx.edu/~alanmi/research/extra.htm.