RexBDDs: Reduction-on-edge complement-and-swap binary decision diagrams
Gianfranco Ciardo, Andrew S. Miner, Lichuan Deng, and 1 more author
In Proc. DAC’24, Jun 2024
We introduce RexBDDs, binary decision diagrams (BDDs) that exploit reduction opportunities well beyond those of reduced ordered BDDs, zero-suppressed BDDs, and recent proposals integrating multiple reduction rules. RexBDDs also leverage (output) complement flags and (input) swap flags to potentially decrease the number of nodes by a factor of four. We define a reduced form of RexBDDs that ensures canonicity, and use a set of benchmarks to demonstrate their superior storage and runtime requirements compared to previous alternatives.