Techniques of BDD/ZDD: Brief History and Recent Activity

Shin-ichi MINATO

doi:10.1587/transinf.E96.D.1419

Open Access
Techniques of BDD/ZDD: Brief History and Recent Activity

Shin-ichi MINATO

Full Text Views

83

Cite this

Free PDF (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 (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale 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 in-memory 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 large-scale 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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.7 pp.1419-1429

Publication Date: 2013/07/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1419

Type of Manuscript: INVITED SURVEY PAPER

Category

Authors

Shin-ichi MINATO
Hokkaido University

Keyword

BDD, ZDD, decision diagram, discrete structure, algorithm, data structure

Cite this

Copy

Shin-ichi MINATO, "Techniques of BDD/ZDD: Brief History and Recent Activity" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 7, pp. 1419-1429, July 2013, doi: 10.1587/transinf.E96.D.1419.
Abstract: 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 (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale 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 in-memory 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 large-scale 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1419/_p

Copy

@ARTICLE{e96-d_7_1419,
author={Shin-ichi MINATO, },
journal={IEICE TRANSACTIONS on Information},
title={Techniques of BDD/ZDD: Brief History and Recent Activity},
year={2013},
volume={E96-D},
number={7},
pages={1419-1429},
abstract={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 (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale 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 in-memory 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 large-scale 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.},
keywords={},
doi={10.1587/transinf.E96.D.1419},
ISSN={1745-1361},
month={July},}

Copy

TY - JOUR
TI - Techniques of BDD/ZDD: Brief History and Recent Activity
T2 - IEICE TRANSACTIONS on Information
SP - 1419
EP - 1429
AU - Shin-ichi MINATO
PY - 2013
DO - 10.1587/transinf.E96.D.1419
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2013
AB - 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 (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale 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 in-memory 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 large-scale 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.
ER -