# Structured d-DNNF Is Not Closed Under Negation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 7 Feb 2024.

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

- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [Connecting Knowledge Compilation Classes and Width Parameters](https://mlsanity.com/paper/1811.02944/) (2018)
- [New Limits for Knowledge Compilation and Applications to Exact Model Counting](https://mlsanity.com/paper/1506.02639/) (2015)
- [Circuit Treewidth, Sentential Decision, and Query Compilation](https://mlsanity.com/paper/1701.04626/) (2017)
- [On the relation between structured d-DNNFs and SDDs](https://mlsanity.com/paper/1912.01430/) (2019)

## Built on by (most cited first, 1 of 1)

- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)

## Abstract (arXiv)

Both structured d-DNNF and SDD can be exponentially more succinct than OBDD. Moreover, SDD is essentially as tractable as OBDD. But this has 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 monotone AC analogue to structured d-DNNF.