Papers › Belief Revision in Sentential Decision Diagrams

Belief Revision in Sentential Decision Diagrams

20 Jan 2022arXiv:2201.08112archive 2025-07-28

Lilith Mattei, Alessandro Facchini, Alessandro Antonucci

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.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

idsia-papers/2021-kr-revision officialmentioned in paperSyntology: not harvested report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

BASE

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections