| 講演名 | 2002/6/17 O(log n)項単調論理和標準形の効率的な双対化について 牧野 和久, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では,O(log n)項単調論理和標準形ψが逐次多項式時間で双対化可能であることを示す.ただし,nはψに現れる変数の数である.この結果は,kが一定の場合に,k項単調論理和標準形が多項式時間で双対化可能であるという簡単な結果の改良である. |
| 抄録(英) | This paper shows that O(log n)-term monotone disjunctive normal forms (DNFs)ψ can be dualized in incremental polynomial time, where n is the number of variables in ψ. This improves upon the trivial result that k-term monotone DNFs can be dualized in polynomial time, where k is bounded by some constant. |
| キーワード(和) | 双対化 / 単調論理関数 / k項論理和標準形 / ハイパーグラフ / 横断計算 / 組合せ列挙 / 全多項式時間アルゴリズム |
| キーワード(英) | Dualization / monotone Boolean function / k-term DNF / hypergraph / transversal computation / combinatorial enumeration / polynomial total time algorithm |
| 資料番号 | COMP2002-19 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/6/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | O(log n)項単調論理和標準形の効率的な双対化について |
| サブタイトル（和） | |
| タイトル（英） | Efficient Dualization of O(log n)-Term Monotone Disjunctive Normal Forms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 双対化 / Dualization |
| キーワード(2)（和/英） | 単調論理関数 / monotone Boolean function |
| キーワード(3)（和/英） | k項論理和標準形 / k-term DNF |
| キーワード(4)（和/英） | ハイパーグラフ / hypergraph |
| キーワード(5)（和/英） | 横断計算 / transversal computation |
| キーワード(6)（和/英） | 組合せ列挙 / combinatorial enumeration |
| キーワード(7)（和/英） | 全多項式時間アルゴリズム / polynomial total time algorithm |
| 第 1 著者 氏名（和/英） | 牧野 和久 / Kazuhisa MAKINO |
| 第 1 著者 所属（和/英） | 大阪大学大学院 基礎工学研究科 Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 2002/6/17 |
| 資料番号 | COMP2002-19 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 140 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |