On the relative succinctness of sentential decision diagrams

DOI10.1007/S00224-018-9904-ZzbMATH Open1435.68320arXiv1802.04544OpenAlexW2963539719WikidataQ128787747 ScholiaQ128787747MaRDI QIDQ2322709FDOQ2322709

Authors: Beate Bollig, Matthias Buttkus 

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: Sentential decision diagrams (SDDs) introduced by Darwiche in 2011 are a promising representation type used in knowledge compilation. The relative succinctness of representation types is an important subject in this area. The aim of the paper is to identify which kind of Boolean functions can be represented by SDDs of small size with respect to the number of variables the functions are defined on. For this reason the sets of Boolean functions representable by different representation types in polynomial size are investigated and SDDs are compared with representation types from the classical knowledge compilation map of Darwiche and Marquis. Ordered binary decision diagrams (OBDDs) which are a popular data structure for Boolean functions are one of these representation types. SDDs are more general than OBDDs by definition but only recently, a Boolean function was presented with polynomial SDD size but exponential OBDD size. This result is strengthened in several ways. The main result is a quasipolynomial simulation of SDDs by equivalent unambiguous nondeterministic OBDDs, a nondeterministic variant where there exists exactly one accepting computation for each satisfying input. As a side effect an open problem about the relative succinctness between SDDs and free binary decision diagrams (FBDDs) which are more general than OBDDs is answered.

Full work available at URL: https://arxiv.org/abs/1802.04544

Recommendations

• Variable shift SDD: a more succinct sentential decision diagram
• On the relation between structured \(d\)-DNNFs and SDDs
• On limitations of structured (deterministic) DNNFs
• Binary decision diagrams
• On the size of binary decision diagrams representing Boolean functions

zbMATH Keywords

complexity theoryordered binary decision diagramsknowledge compilationdecomposable negation normal formssentential decision diagramsstorage access functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Knowledge representation (68T30)

Cites Work

• Graph-Based Algorithms for Boolean Function Manipulation
• Title not available (Why is that?)
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Title not available (Why is that?)
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph driven BDDs -- a new data structure for Boolean functions
• On the read-once property of branching programs and CNFs of bounded treewidth
• Title not available (Why is that?)
• Decomposable negation normal form
• On the size of binary decision diagrams representing Boolean functions
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• On the relative succinctness of sentential decision diagrams
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• The language of search
• Efficient data structures for Boolean functions
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Binary decision diagrams

Cited In (13)

• On the relative succinctness of sentential decision diagrams
• Sequence sentential decision diagrams
• New canonical representations by augmenting OBDDs with conjunctive decomposition
• A faster implementation of EQ and SE queries for switch-list representations
• Connecting knowledge compilation classes and width parameters
• On limitations of structured (deterministic) DNNFs
• Variable shift SDD: a more succinct sentential decision diagram
• Symmetry-driven decision diagrams for knowledge compilation
• On the (complete) reasons behind decisions
• Minimization of Word-Level Decision Diagrams
• Efficient computation of shap explanation scores for neural network classifiers via knowledge compilation
• On quantifying literals in Boolean logic and its applications to explainable AI
• On the relation between structured \(d\)-DNNFs and SDDs

This page was built for publication: On the relative succinctness of sentential decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322709)