Structured d-DNNF Is Not Closed under Negation
Structured d-DNNF Is Not Closed under Negation
Harry Vinall-Smeeth
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3593-3601.
https://doi.org/10.24963/ijcai.2024/398
Both structured d-DNNF and SDD can be exponentially more succinct than OBDD. Moreover, SDD is essentially as tractable as OBDD. But this leaves left two important open questions. Firstly, does OBDD support more tractable transformations than structured d-DNNF? And secondly, is structured d-DNNF more succinct than SDD? In this paper, we answer both questions in the affirmative. For the first question we show that, unlike OBDD, structured d-DNNF does not support polytime negation, disjunction, or existential quantification operations. As a corollary, we deduce that there are functions with an equivalent polynomial-sized structured d-DNNF but with no such representation as an SDD, thus answering the second question. We also lift this second result to arithmetic circuits (AC) to show a succinctness gap between PSDD and the positive AC analogue to structured d-DNNF.
Keywords:
Knowledge Representation and Reasoning: KRR: Knowledge compilation