A novel minimization method for sentential decision diagrams
it - Information Technology · 26.05.2025 · 67 (2-3) · 107-114
DOI: 10.1515/itit-2025-0032 ↗Kurz gefasst
Fachartikel in der Zeitschrift it - Information Technology, online erschienen am 12.03.2026. Verfasst von Joseph Clark und 1 weiteren Autor:innen. Die Arbeit nennt 10 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF CAREER Award.
Abstract (Originalsprache)
Sentential Decision Diagrams (SDDs) are a generalization of Binary Decision Diagrams (BDDs) that allow decisions based on “sentences” of variables, rather than only individual variables. SDDs are ordered based on a binary tree of variables (a vtree) which can represent their more complex structure. Like BDDs, the order of an SDD significantly impacts its size. We present two novel SDD minimization methods based on Rudell’s sifting algorithm and a symmetric sifting algorithm, both of which are BDD minimization methods. To evaluate the performance of our proposed techniques, we compile the combinational benchmarks from the LGSynth’91 benchmark set and dynamically minimize each circuit with our proposed techniques and two variations of the current state-of-the-art method. Our methods show an average improvement ratio of 20.2 % in SDD size compared with the current state-of-the-art technique. For larger circuits (≥50 inputs), the improvement ratio increases to 39.2 %.
Förderung
- NSF CAREER Award
Zitieren
APA
Clark, J., & Thapliyal, H. (2025). A novel minimization method for sentential decision diagrams. it - Information Technology, 67(2-3), 107-114. https://doi.org/10.1515/itit-2025-0032
Vancouver
Clark J, Thapliyal H. A novel minimization method for sentential decision diagrams. it - Information Technology. 2025;67(2-3):107-114. doi:10.1515/itit-2025-0032
BibTeX
@article{Clark2025,
author = {Clark, Joseph and Thapliyal, Himanshu},
title = {A novel minimization method for sentential decision diagrams},
journal = {it - Information Technology},
year = {2025},
volume = {67},
number = {2-3},
pages = {107--114},
doi = {10.1515/itit-2025-0032}
}
EUVIMED