Belief Revision in Sentential Decision Diagrams
Belief revision is the task of modifying a knowledge base when new information becomes available, while also respecting a number of desirable properties. Classical belief revision schemes have been already specialised to \emph{binary decision diagrams} (BDDs), the classical formalism to compactly represent propositional knowledge. These results also apply to \emph{ordered} BDDs (OBDDs), a special class of BDDs, designed to guarantee canonicity. Yet, those revisions cannot be applied to \emph{sentential decision diagrams} (SDDs), a typically more compact but still canonical class of Boolean circuits, which generalizes OBDDs, while not being a subclass of BDDs. Here we fill this gap by deriving a general revision algorithm for SDDs based on a syntactic characterisation of Dalal revision. A specialised procedure for DNFs is also presented. Preliminary experiments performed with randomly generated knowledge bases show the advantages of directly perform revision within SDD formalism.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Variants of Tagged Sentential Decision Diagrams
A recently proposed canonical form of Boolean functions, namely tagged sentential decision diagrams (TSDDs), exploits both the standard and zero-suppressed trimming rules. The standard ones minimize the size of sententia…
Tractable Inference in Credal Sentential Decision Diagrams
Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. They allow for a compact representation of joint probability mass functions defined…
Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption
Probabilistic sentential decision diagrams are a class of structured-decomposable probabilistic circuits especially designed to embed logical constraints. To adapt the classical LearnSPN scheme to learn the structure of …
ClusteringOn the Relative Succinctness of Sentential Decision Diagrams
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…
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called $c$-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each $k$ there is a class of CNF…