SDD: A New Canonical Representation of Propositional Knowledge Bases
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 819-825.
Abstract
We identify a new representation of propositional knowledge bases, the Sentential Decision Diagram SDD, which is interesting for a number of reasons. First, it is canonical in the presence of additional properties that resemble reduction rules of OBDDs. Second, SDDs can be combined using any Boolean operator in polytime. Third, CNFs with n variables and treewidth w have canonical SDDs of size O(n 2w), which is tighter than the bound on OBDDs based on pathwidth. Finally, every OBDD is an SDD. Hence, working with the latter does not preclude the former.
@inproceedings{ijcai2011p143,
title = {SDD: A New Canonical Representation of Propositional Knowledge Bases},
author = {Darwiche, Adnan},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {819--825},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-143},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-143},
}
TY - CPAPER TI - SDD: A New Canonical Representation of Propositional Knowledge Bases AU - Darwiche, Adnan T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 819 EP - 825 DO - 10.5591/978-1-57735-516-8/IJCAI11-143 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-143 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
