Computational Complexity of Manipulating Binary Decision Diagrams

Yasuhiko TAKENAGA; Shuzo YAJIMA

Computational Complexity of Manipulating Binary Decision Diagrams

Yasuhiko TAKENAGA, Shuzo YAJIMA

Full Text Views

0

Cite this

Summary :

An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC¹-reducible to REACHABILITY. That is, both of the problems belong to NC². In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC¹-reducible to REACHBILITY.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.6 pp.642-647

Publication Date: 1994/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Yasuhiko TAKENAGA, Shuzo YAJIMA, "Computational Complexity of Manipulating Binary Decision Diagrams" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 6, pp. 642-647, June 1994, doi: .
Abstract: An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC¹-reducible to REACHABILITY. That is, both of the problems belong to NC². In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC¹-reducible to REACHBILITY.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_6_642/_p

Copy

@ARTICLE{e77-d_6_642,
author={Yasuhiko TAKENAGA, Shuzo YAJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Computational Complexity of Manipulating Binary Decision Diagrams},
year={1994},
volume={E77-D},
number={6},
pages={642-647},
abstract={An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC¹-reducible to REACHABILITY. That is, both of the problems belong to NC². In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC¹-reducible to REACHBILITY.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Computational Complexity of Manipulating Binary Decision Diagrams
T2 - IEICE TRANSACTIONS on Information
SP - 642
EP - 647
AU - Yasuhiko TAKENAGA
AU - Shuzo YAJIMA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1994
AB - An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC¹-reducible to REACHABILITY. That is, both of the problems belong to NC². In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC¹-reducible to REACHBILITY.
ER -