SDDs Are Exponentially More Succinct than OBDDs

The choice of the target data structure involves an unavoidable tradeoff between succinctness and where the variable x is not in the variable set Y. tractability. Indeed, SDDs properly contain OBDDs, and hence are Darwiche and Marquis (2002) systematically investigated at least as succinct as OBDDs, while preserving tractability this tradeoff in the fundamental case where the knowledge of all key tasks that are tractable on OBDDs. For this bases are boolean functions and the data structures are classes reason, they have been used in a variety of applications of boolean circuits (representation languages). in artificial intelligence and probabilistic reasoning, as reported, In their setting, decomposable negation normal forms for instance, by (Van den Broek and Darwiche 2015; (DNNFs) and ordered binary decision diagrams (OBDDs) Oztok and Darwiche 2015).