Implicit Representation and Manipulation of Binary Decision Diagrams (Special Section of Selected Papers from the 8th Karuizawa Workshop on Circuits and Systems)

概要

論文の詳細を見る
This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new efficient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD representation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to manipulate Boolean functions on this implicit data structure.
社団法人電子情報通信学会の論文
1996-03-25