BDD

論理関数を表すデータ構造.

ZDD (Zero-suppressed BDD) は集合族を表すバリアント
ZDD上で union や inersection, difference を圧縮したまま計算できる
- 圧縮したまま計算するには簡約化(= 冗長な節点が無く, 唯一性が保証)されている必要がある
トップダウンに構築されたBDDで冗長性が発生しやすく, 演算毎に簡約化が必要
- 簡約化のアルゴリズムは Knuth09 が提案, $O (N)$
これを高速に行いたい
- ハードウェアによる高速化
- ours: 並列準簡約化と追駆簡約化による新しい並列化
  - 先行研究の並列化とは直交する手法
    - 直交(orthogonal): 因果関係がない, 別問題の

参考文献