ORDERED KRONECKER FUNCTIONAL DECISION DIAGRAMS - A DATA STRUCTURE FORREPRESENTATION AND MANIPULATION OF BOOLEAN FUNCTIONS

Ordered Kronecker functional decision diagrams (OKFDD's) are a data st ructure for efficient representation and manipulation of Boolean funct ions. OKFDD's are a generalization of ordered binary decision diagrams (OBDD's) and ordered functional decision;diagrams and thus combine th e advantages of both. In this paper, basic properties of OKFDD's and t heir efficient representation and manipulation are given. Starting wit h elementary manipulation algorithms, we present methods for the const ruction of small OKFDD's. Our approach is based on dynamic variable or dering and decomposition-type choice. For changing the decomposition t ype, we use an efficient reordering-based method. We briefly discuss t he implementation of PUMA, an OKFDD package, which was used in all our experiments, These experiments demonstrate the quality of our methods in comparison to sifting and interleaving for OBDD's.