Presentation | 1996/7/25 Size and Variable Ordering of OBDDs Representing Threshold Functions Yasuhiko TAKENAGA, Mitsushi NOUZOE, Shuzo YAJIMA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In representing various Boolean functions using OBDDs, the larger the sizes of OBDDs are, the more difficult it is to deal with them because of the memory requirements. Therefore, it is important to investigate the size of OBDDs representing various Boolean functions. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We prove an Ω(n2^ |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | ordered binary decision diagram / threshold function / lower bound / variable ordering |
Paper # | COMP96-24 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1996/7/25(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Size and Variable Ordering of OBDDs Representing Threshold Functions |
Sub Title (in English) | |
Keyword(1) | ordered binary decision diagram |
Keyword(2) | threshold function |
Keyword(3) | lower bound |
Keyword(4) | variable ordering |
1st Author's Name | Yasuhiko TAKENAGA |
1st Author's Affiliation | Graduate School of Engineering,Kyoto University() |
2nd Author's Name | Mitsushi NOUZOE |
2nd Author's Affiliation | Graduate School of Engineering,Kyoto University |
3rd Author's Name | Shuzo YAJIMA |
3rd Author's Affiliation | Graduate School of Engineering,Kyoto University |
Date | 1996/7/25 |
Paper # | COMP96-24 |
Volume (vol) | vol.96 |
Number (no) | 196 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |