Structured Decomposable Negation Normal Form (structured-DNNF for short) is a circuit representation of Boolean functions introduced by Pipatsrisawat and Darwiche (2008) and have been widely used for Knowledge Compilation. structured-DNNFs generalize nondeterministic ordered binary decision diagrams (nOBDDs for short) and are super-polynomially more powerful. This talk aims to provide more structural insights into functions computed by structured-DNNFs and nOBDDs.

We obtain fundamental results on the structure of these classes by looking at the underlying circuit. In particular:
- We prove a size-efficient depth reduction for structured-DNNFs and DNNFs. Our result implies a quasi-polynomial simulation of structured-DNNFs by nOBDDs which in turn yields an asymptotically tight separation between nOBDDs and structured-DNNFs.
- We obtain restrictions on the underlying circuit of structured-DNNF and on the underlying vtree such that the resulting restrictions are computationally equivalent to nOBDDs.

Our results provide more structural insights into the knowledge compilation class represented by structured-DNNFs as target models.