Belief Revision in Sentential Decision Diagrams
This work addresses a gap in belief revision for knowledge representation, specifically for SDDs, which are used in AI and logic, but it is incremental as it extends existing methods from BDDs to SDDs.
The paper tackles the problem of belief revision for sentential decision diagrams (SDDs), which are more compact than binary decision diagrams (BDDs) but lacked a revision algorithm, by deriving a general revision algorithm based on Dalal revision and showing advantages through preliminary experiments with randomly generated knowledge bases.
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.