[Zurück]

S. Bova:
"SDDs Are Exponentially More Succinct than OBDDs";
Vortrag: AAAI Conference, Phoenix, Arizona, USA; 12.02.2016 - 17.02.2016; in: "Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence", (2016), ISBN: 978-1-57735-760-5; S. 929 - 935.

Introduced by Darwiche (2011), sentential decision diagrams
(SDDs) are essentially as tractable as ordered binary decision
diagrams (OBDDs), but tend to be more succinct in practice.
This makes SDDs a prominent representation language, with
many applications in artificial intelligence and knowledge
compilation.
We prove that SDDs are more succinct than OBDDs also in
theory, by constructing a family of boolean functions where
each member has polynomial SDD size but exponential OBDD
size. This exponential separation improves a quasipolynomial
separation recently established by Razgon (2014a), and settles
an open problem in knowledge compilation (Darwiche 2011).

http://publik.tuwien.ac.at/files/publik_254753.pdf