论文标题
句子决策图中的信念修订
Belief Revision in Sentential Decision Diagrams
论文作者
论文摘要
信念修订是当新信息可用时修改知识库的任务，同时还尊重许多理想的属性。古典信念修订方案已经专门针对\ emph {二进制决策图}（BDDS），这是经典的形式主义，以压缩命题知识。这些结果还适用于\ emph {order} bdds（obdds），这是一种特殊的BDD类别，旨在保证规范。然而，这些修订不能应用于\ emph {句子决策图}（SDDS），这是一种通常更紧凑但仍然是规范的布尔电路类别，它概括了OBDD，而不是BDD的子类。在这里，我们通过基于dalal修订的句法表征得出SDD的常规修订算法来填补这一空白。还提出了针对DNF的专门程序。通过随机生成的知识库进行的初步实验表明，在SDD形式主义中直接进行修订的优势。
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.
