ML Anthology

SDD: A New Canonical Representation of Propositional Knowledge Bases

Adnan Darwiche
IJCAI 2011 pp. 819-826
doi:10.5591/978-1-57735-516-8/IJCAI11-143 /ijcai/2011/darwiche2011ijcai-sdd/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Darwiche. "SDD: A New Canonical Representation of Propositional Knowledge Bases." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-143

Markdown

[Darwiche. "SDD: A New Canonical Representation of Propositional Knowledge Bases." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/darwiche2011ijcai-sdd/) doi:10.5591/978-1-57735-516-8/IJCAI11-143

BibTeX

@inproceedings{darwiche2011ijcai-sdd,
  title     = {{SDD: A New Canonical Representation of Propositional Knowledge Bases}},
  author    = {Darwiche, Adnan},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {819-826},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-143},
  url       = {https://mlanthology.org/ijcai/2011/darwiche2011ijcai-sdd/}
}