  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.
