
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Techniques of BDD/ZDD: Brief History and Recent Activity
Shinichi MINATO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.7
pp.14191429 Publication Date: 2013/07/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.1419
Print ISSN: 09168532 Type of Manuscript: INVITED SURVEY PAPER Category: Keyword: BDD, ZDD, decision diagram, discrete structure, algorithm, data structure,
Full Text: FreePDF(1.2MB)
Summary:
Discrete structures are foundational material for computer science and mathematics, which are related to set theory, symbolic logic, inductive proof, graph theory, combinatorics, probability theory, etc. Many problems solved by computers can be decomposed into discrete structures using simple primitive algebraic operations. It is very important to represent discrete structures compactly and to execute efficiently tasks such as equivalency/validity checking, analysis of models, and optimization. Recently, BDDs (Binary Decision Diagrams) and ZDDs (Zerosuppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate largescale combinational logic data, which are the basic discrete structures in various fields of application. Although a quarter of a century has passed since Bryant's first idea, there are still a lot of interesting and exciting research topics related to BDD and ZDD. BDD/ZDD is based on inmemory data processing techniques, and it enjoys the advantage of using random access memory. Recent commodity PCs are equipped with gigabytes of main memory, and we can now solve largescale problems which used to be impossible due to memory shortage. Thus, especially since 2000, the scope of BDD/ZDD methods has increased. This survey paper describes the history of, and recent research activity pertaining to, techniques related to BDD and ZDD.

