著者

戸田貴久

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2013-AL-145, no.3, pp.1-8, 2013-10-30

---

論理関数の CNF が与えられるとき,その論理式を表す二分決定グラフ BDD を構築するための新しい手法を提案する.CNF は従来から用いられている論理関数の伝統的な表現法の一つである.BDD には論理関数を操作するための様々な演算が備わっているので,CNF よりも BDD を用いる方が適切な多くの問題がある.しかし,CNF から BDD の構築は自明な計算ではない.本稿では,まず CNF を表す中間表現を計算し,それから BDD に変換する二段階の BDD 構築法を提案する.さらに,提案法で中間表現として用いられるデータ構造は,BDD 構築だけでなく,有向グラフ上の列挙問題など様々な問題に対して有用であることも示す.