# On the relation between structured d-DNNFs and SDDs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2019.

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

- [Structured d-DNNF Is Not Closed Under Negation](https://mlsanity.com/paper/2402.04832/) (2024)
- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)

## Abstract (arXiv)

Structured d-DNNFs and SDDs are restricted negation normal form circuits used in knowledge compilation as target languages into which propositional theories are compiled. Structuredness is imposed by so-called vtrees. By definition SDDs are restricted structured d-DNNFs. Beame and Liew (2015) as well as Bova and Szeider (2017) mentioned the question whether structured d-DNNFs are really more general than SDDs w.r.t. polynomial-size representations (w.r.t. the number of Boolean variables the represented functions are defined on.) The main result in the paper is the proof that a function can be represented by SDDs of polynomial size if the function and its complement have polynomial-size structured d-DNNFs that respect the same vtree.