| 講演名 | 1996/7/25 しきい値関数を表す二分決定グラフのサイズと変数順序 武永 康彦, 農添 三資, 矢島 脩三, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 二分決定グラフはグラフによる論理関数の表現法の一つである。二分決定グラフを用いて論理関数を表現する場合、そのサイズが大きくなると記憶量の点から処理が困難になる。そのため、種々の関数を表現するために必要となる二分決定グラフのサイズに関する研究が重要である。本稿では、しきい値関数を表現する二分決定グラフのサイズについて考察する。しきい値関数を表現する二分決定グラフのサイズの下界がΩ(n2^ |
| 抄録(英) | 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^ |
| キーワード(和) | 二分決定グラフ / しきい値関数 / 下界 / 変数順序付け |
| キーワード(英) | ordered binary decision diagram / threshold function / lower bound / variable ordering |
| 資料番号 | COMP96-24 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/7/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | しきい値関数を表す二分決定グラフのサイズと変数順序 |
| サブタイトル（和） | |
| タイトル（英） | Size and Variable Ordering of OBDDs Representing Threshold Functions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 二分決定グラフ / ordered binary decision diagram |
| キーワード(2)（和/英） | しきい値関数 / threshold function |
| キーワード(3)（和/英） | 下界 / lower bound |
| キーワード(4)（和/英） | 変数順序付け / variable ordering |
| 第 1 著者 氏名（和/英） | 武永 康彦 / Yasuhiko TAKENAGA |
| 第 1 著者 所属（和/英） | 京都大学 工学部 情報工学教室 Graduate School of Engineering,Kyoto University |
| 第 2 著者 氏名（和/英） | 農添 三資 / Mitsushi NOUZOE |
| 第 2 著者 所属（和/英） | 京都大学 工学部 情報工学教室 Graduate School of Engineering,Kyoto University |
| 第 3 著者 氏名（和/英） | 矢島 脩三 / Shuzo YAJIMA |
| 第 3 著者 所属（和/英） | 京都大学 工学部 情報工学教室 Graduate School of Engineering,Kyoto University |
| 発表年月日 | 1996/7/25 |
| 資料番号 | COMP96-24 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 196 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |