A CHARACTERIZATION OF BINARY DECISION DIAGRAMS

被引：12

作者：

CHAKRAVARTY, S

机构：

[1] Department of Computer Science, State University of New York, Buffalo

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1993年 / 42卷 / 02期

基金：

美国国家科学基金会;

关键词：

BINARY DECISION DIAGRAMS; COMPLEXITY RESULTS; FREE BDDS; OBDDS; REPEATED BDDS;

D O I：

10.1109/12.204789

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Binary Decision Diagrams (BDD's) are a representation of Boolean functions. Its use in the synthesis, simulation and testing of Boolean circuits has been proposed by various researchers. In all these applications of BDD's solutions to some fundamental computational problems are needed. We present a characterization of BDD's in terms of the complexity of these computational problems. A tighter bound on the size of an Ordered BDD that can be computed from a given Boolean Circuit is presented. Based on our results we make a case for exploring the use of Repeated BDD's, with a small number of Repeated Variables, and Free BDD's for some applications for which only Ordered BDD's have be used so far.

引用

页码：129 / 137

页数：9

共 33 条

[1] FUNCTIONAL TEST GENERATION FOR DIGITAL CIRCUITS DESCRIBED USING BINARY DECISION DIAGRAMS. [J].

Abadir, Magdy S. ;

Reghbati, Hassan K. .

IEEE Transactions on Computers, 1986, C-35 (04) :375-379

[2]

AHO A, 1979, PRINCIPLES COMPILER

[3]

Akers S. B., 1980, 10th International Symposium on Fault-Tolerant Computing, P65

[4]

AKERS SB, 1978, IEEE T COMPUT, V27, P509, DOI 10.1109/TC.1978.1675141

[5]

AKERS SB, 1978, 8TH P INT S FAULT TO, P82

[6]

ASHAR P, 1991, MAR P SANT CRUZ C AD, P35

[7] ORDERED BINARY DECISION DIAGRAMS AND CIRCUIT STRUCTURE EXTENDED ABSTRACT [J].

BERMAN, CL .

PROCEEDINGS - IEEE INTERNATIONAL CONFERENCE ON COMPUTER DESIGN : VLSI IN COMPUTERS & PROCESSORS, 1989, :392-395

[8]

BHATTACHARYA B, 1987, 17TH P IEEE ACM INT, P264

[9] EQUIVALENCE OF FREE BOOLEAN GRAPHS CAN BE DECIDED PROBABILISTICALLY IN POLYNOMIAL-TIME [J].

BLUM, M ;

CHANDRA, AK ;

WEGMAN, MN .

INFORMATION PROCESSING LETTERS, 1980, 10 (02) :80-82

[10]

Brace K. S., 1990, 27th ACM/IEEE Design Automation Conference. Proceedings 1990 (Cat. No.90CH2894-4), P40, DOI 10.1109/DAC.1990.114826

← 1 2 3 4 →