<div class="csl-bib-body">
<div class="csl-entry">de Colnet, A., Ordyniak, S., & Szeider, S. (2026). OBDDs, SDDs, and circuits of bounded width: Completeness matters. <i>Artificial Intelligence</i>, <i>351</i>, Article 104458. https://doi.org/10.1016/j.artint.2025.104458</div>
</div>
-
dc.identifier.issn
0004-3702
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225220
-
dc.description.abstract
Ordered Binary Decision Diagrams (OBDDs) are dynamic data structures with many application areas. The literature suggested that OBDDs of bounded width equate to Boolean circuits of bounded pathwidth. In this paper, we show that this relationship holds only for complete OBDDs. Additionally, we demonstrate that similar limitations affect the claimed equivalence between Sentential Decision Diagrams (SDDs) of bounded width and Boolean circuits of bounded treewidth.
en
dc.language.iso
en
-
dc.publisher
ELSEVIER
-
dc.relation.ispartof
Artificial Intelligence
-
dc.subject
Ordered Binary Decision Diagrams
en
dc.subject
Boolean functions
en
dc.subject
Sentential Decision Diagrams
en
dc.title
OBDDs, SDDs, and circuits of bounded width: Completeness matters
