Metraipolis › archive › dc_cc162bf1c9ce

XBDD: A Highly Optimized ROBDD with Per-Edge Variable-Flip Maps — arXiv:2609.36778

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.36778
License (as archived)
CC0-1.0
Archived
2026-10-07T19:18:59.593Z
SHA-256 of the archived text
0ba5aac324b4ce97410c46a51962d805e6640cc6e5aaad7c09997c62de595a0d
Stable URL of this page
https://metraipolis.com/documento/dc_cc162bf1c9ce

How to cite

XBDD: A Highly Optimized ROBDD with Per-Edge Variable-Flip Maps — arXiv:2609.36778 — arXiv (en), https://arxiv.org/abs/2609.36778 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cc162bf1c9ce (Metraipolis archive dc_cc162bf1c9ce, sha256 0ba5aac324b4ce97410c46a51962d805e6640cc6e5aaad7c09997c62de595a0d)
BibTeX
@misc{dccc162bf1c9ce,
  title = {XBDD: A Highly Optimized ROBDD with Per-Edge Variable-Flip Maps — arXiv:2609.36778},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.36778},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cc162bf1c9ce; sha256 0ba5aac324b4ce97410c46a51962d805e6640cc6e5aaad7c09997c62de595a0d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36778. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Reduced Ordered Binary Decision Diagram (ROBDD) is a canonical representation of Boolean functions and is widely used in tasks such as equivalence checking and satisfiability checking of combinational circuits. Classical ROBDD packages greatly improve the efficiency of building ROBDDs through a series of optimization techniques, and compress the node scale of the ROBDD through complement edges. However, existing implementations do not take into account the local polarity differences of isomorphic Boolean functions, and still produce a distinct node for each polarity combination, thereby causing an explosion in the number of nodes. This paper proposes XBDD, a highly optimized ROBDD that, on the basis of fully implementing complement edges and their accompanying engineering techniques, introduces a per-edge variable-flip map. XBDD attaches a flip map to each edge to indicate which input variables must be negated when that edge is followed. This allows nodes that differ only in local input polarities to be merged, further reducing the node count. For certain function families, this sharing even yields exponential compression. We also propose methods that use a bitmap and a map pool to substantially reduce the extra overhead brought by the map, and propose normalization and cofactor operators for the map. In addition, XBDD implements several other engineering optimizations to further improve both time and space efficiency. Experiments show that XBDD trades a controllable time cost for a significant space gain, validating the effectiveness of the per-edge variable-flip map.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.36778 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T18:45:07.081Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).