TU Bergakademie Freiberg | Fakultät für Mathematik und Informatik

1. Workshop Boolesche Probleme

R. Drechsler, M. Theobald, B. Becker, Computer Science Department, Johann Wolfgang Goethe-University, D-60054 Frankfurt am Main, Germany

A. Sarabi, M.A. Perkowski, Department of Electrical Engineering, Portland State University, Portland, OR 97207-0751, USA

Abstract
A package for efficient representation and manipulation of Boolean functions based on Ordered Kronecker Functional Decision Diagrams (OKFDDs) has been introduced [7].OKFDDs are a more general data structure than Ordered Binary Decision Diagrams (OBDDs) and Ordered Functional Decision Diagrams (OFDDs). In this paper, the computational power of this new representation is investigated both theoretically and experimentally. It is shown that there exists a class of functions for which OBDDs and OFDDs are both exponential while OKFDDs are polynomial. Furthermore, the compactness of OKFDDs is shown for large benchmarks examples for which an average of 35% reduction in size is archived for OKFDDs over OBDDs. The reductions of up to 75% are reported, all starting from random variable ordering. A variation of sifting which allows to set lower and upper bounds is also shown to be advantageous for OKFDDs as well as OBDDs.