しきい値関数を表す二分決定グラフのサイズと変数順序
スポンサーリンク
概要
- 論文の詳細を見る
二分決定グラフはグラフによる論理関数の表現法の一つである。二分決定グラフを用いて論理関数を表現する場合、そのサイズが大きくなると記憶量の点から処理が困難になる。そのため、種々の関数を表現するために必要となる二分決定グラフのサイズに関する研究が重要である。本稿では、しきい値関数を表現する二分決定グラフのサイズについて考察する。しきい値関数を表現する二分決定グラフのサイズの下界がΩ(n2^<cn^<1-ε>>)であることを示す。また、重みの全順序だけを用いたのでは、良い変数順序が得られないことも示す。
- 社団法人電子情報通信学会の論文
- 1996-07-25
著者
-
矢島 脩三
京都大学工学部情報工学教室
-
矢島 脩三
京都大学大学院工学研究科情報工学教室
-
矢島 脩三
京都大学 工学部
-
武永 康彦
電気通信大学情報工学科
-
農添 三資
京都大学大学院工学研究科:(現)松下電器産業株式会社
-
武永 康彦
京都大学 工学部 情報工学教室
-
農添 三資
京都大学 工学部 情報工学教室
関連論文
- 有限オートマトンと表現等価な正則時相論理とその論理設計検証への応用
- 正則時相論理のモデルチェック法の改良と設計検証への適用
- 連想メモリを利用したハードウェア向き単一化アルゴリズム
- 連想メモリを利用した高速単一化アルゴリズム
- 入力制約監視機能をもつ会話型シミュレーション・システムISS
- 京都大学情報処理教育センターの概要
- 複数の二分決定グラフを用いたNP完全な組合せ問題の解法
- 2)超高精細マルチ画像顕微鏡装置の開発(ヒューマンインフォメーション研究会)
- 超高精細マルチ画像顕微鏡装置の開発
- 関係データベースにおける意味制約を反映した非正規形の関係の設計問題