Zero-Suppressed Sentential Decision Diagrams

Authors

  • Masaaki Nishino NTT Corporation
  • Norihito Yasuda Hokkaido University
  • Shin-ichi Minato Hokkaido University
  • Masaaki Nagata NTT Corporation

DOI:

https://doi.org/10.1609/aaai.v30i1.10114

Keywords:

Knowledge Compilation, Binary Decision Diagrams, Propositional Knowledge Base, Sentential Decision Diagrams

Abstract

The Sentential Decision Diagram (SDD) is a prominent knowledge representation language that subsumes the Ordered Binary Decision Diagram (OBDD) as a strict subset. Like OBDDs, SDDs have canonical forms and support bottom-up operations for combining SDDs, but they are more succinct than OBDDs. In this paper we introduce an SDD variant, called the Zero-suppressed Sentential Decision Diagram (ZSDD). The key idea of ZSDD is to employ new trimming rules for obtaining a canonical form. As a result, ZSDD subsumes the Zero-suppressed Binary Decision Diagram (ZDD) as a strict subset. ZDDs are known for their effectiveness on representing sparse Boolean functions. Likewise, ZSDDs can be more succinct than SDDs when representing sparse Boolean functions. We propose several polytime bottom-up operations over ZSDDs, and a technique for reducing ZSDD size, while maintaining applicability to important queries. We also specify two distinct upper bounds on ZSDD sizes; one is derived from the treewidth of a CNF and the other from the size of a family of sets. Experiments show that ZSDDs are smaller than SDDs or ZDDs for a standard benchmark dataset.

Downloads

Published

2016-02-21

How to Cite

Nishino, M., Yasuda, N., Minato, S.- ichi, & Nagata, M. (2016). Zero-Suppressed Sentential Decision Diagrams. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10114

Issue

Section

Technical Papers: Knowledge Representation and Reasoning