論理式と二分決定グラフの表現能力の比較
スポンサーリンク
概要
- 論文の詳細を見る
本稿では積和形 (和積形、積環和形) 論理式では多項式サイズで表現できるが二分決定グラフ (OBDD: Ordered Binary Decision Diagram) ではどのような変数順序でも多項式サイズでは表現できない論理関数を示し、二分決定グラフの表現能力と積和形 (和積形、積環和形) 論理式の表現能力が比較不能であることを示す。
- 社団法人電子情報通信学会の論文
- 1997-03-06
著者
-
矢島 脩三
京都大学工学部情報工学教室
-
矢島 脩三
京都大学大学院工学研究科情報工学教室
-
武永 康彦
京都大学大学院工学研究科
-
武永 康彦
電気通信大学情報工学科
-
坊野 博典
京都大学大学院工学研究科
関連論文
- 有限オートマトンと表現等価な正則時相論理とその論理設計検証への応用
- 正則時相論理のモデルチェック法の改良と設計検証への適用
- 連想メモリを利用したハードウェア向き単一化アルゴリズム
- 連想メモリを利用した高速単一化アルゴリズム
- 入力制約監視機能をもつ会話型シミュレーション・システムISS
- 京都大学情報処理教育センターの概要
- 複数の二分決定グラフを用いたNP完全な組合せ問題の解法
- 2)超高精細マルチ画像顕微鏡装置の開発(ヒューマンインフォメーション研究会)
- 超高精細マルチ画像顕微鏡装置の開発
- 関係データベースにおける意味制約を反映した非正規形の関係の設計問題