Computational Complexity of Manipulating Binary Decision Diagrams
スポンサーリンク
概要
- 論文の詳細を見る
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^1-reducible to REACHABILITY. That is, both of the problems belong to NC^2. 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^1-reducible to REACHABILITY.
- 社団法人電子情報通信学会の論文
- 1994-06-25
著者
-
TAKENAGA Yasuhiko
Faculty of Information Science, Kyoto University
-
YAJIMA Shuzo
Faculty of Information Science, Kyoto University
-
Yajima Shuzo
Faculty Of Engineering Kyoto University
-
Takenaga Yasuhiko
Faculty Of Engineering Kyoto University
関連論文
- Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses (Special Section on Discrete Mathematics and Its Applications)
- Formal Design Verification of Combinational Circuits Specified by Recurrence Equations (Special Issue on Synthesis and Verification of Hardware Design)
- Computational Complexity of Manipulating Binary Decision Diagrams
- On Parallel Computation Time of Unification for Restricted Terms
- On the Computational Power of Binary Decision Diagrams
- Hardware Algorithms and Logic Design Automation : An Overview and Progress Report
- Area-Time Efficient Evaluation of Elementary Functions
- Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
- Compaction of Test Sets for Combinatinal Circuits Based on Symbolic Fault Simulation (Special Issue on Synthesis and Verification of Hardware Design)