# Belief Revision in Sentential Decision Diagrams

arXiv: https://arxiv.org/abs/2201.08112 · HTML: https://mlsanity.com/paper/2201.08112/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 14 references that are in the map.
- First posted on arXiv 20 Jan 2022.

## Builds on (most cited first, 1 of 1)

- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)

## Abstract (arXiv)

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 binary decision diagrams (BDDs), the classical formalism to compactly represent propositional knowledge. These results also apply to ordered BDDs (OBDDs), a special class of BDDs, designed to guarantee canonicity. Yet, those revisions cannot be applied to 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.