情報処理学会 第76回全国大会講演要旨

湊らが1991年に提案したSBDDの入力反転エッジは、SBDDのデータ構造を効率的に
扱うためのグラフの一つの属性である。論理式の二分決定木ではノードに命題変
数が配され、出矢印にその命題変数のとる真理値が割り振られる。入力反転エッ
ジは同一の高さを持つ真理値だけが反転している同型の木構造へ入る矢印を意味
している。本研究では変数順序を入れ替えることで入力反転エッジが構成できる
木構造に注目し、こうした状況で変数順序を入れ替えることができることを指摘し、そのアルゴリズムと入れ替え可能な状況について報告する。