Decision \textsc{ dnnf} (a.k.a. $\wedge_d$-\textsc{ fbdd}) is an important special case of Decomposable Negation Normal Form (\textsc{ dnnf}), a landmark knowledge compilation model. Like other known \textsc{ dnnf} restrictions, Decision \textsc{ dnnf} admits \textsc{ fpt} sized representation of \textsc{ cnf}s of bounded \emph{ primal} treewidth. However, unlike other restrictions, the complexity of representation for \textsc{ cnf}s of bounded \emph{ incidence} treewidth is wide open. In[arxiv:1708.07767], we resolved this question for two restricted classes of Decision \textsc{ dnnf} that we name $\wedge_d$-\textsc{ obdd} and Structured Decision \textsc{ dnnf}. In particular, we demonstrated that, while both these classes have \textsc{ fpt}-sized representations for \textsc{ cnf}s of bounded primal treewidth, they need \textsc{ xp}-size for representation of \textsc{ cnf}s of bounded incidence treewidth. In the main part of this paper we carry out an in-depth study of the $\wedge_d$-\textsc{ obdd} model. We formulate a generic methodology for proving lower bounds for the model. Using this methodology, we reestablish the \textsc{ xp} lower bound provided in [arxiv:1708.07767]. We also provide exponential separations between \textsc{ fbdd} and $\wedge_d$-\textsc{ obdd} and between $\wedge_d$-\textsc{ obdd} and an ordinary \textsc{ obdd}. We study the complexity of Apply operation for $\wedge_d$-\textsc{ obdd}. While, in general, the Apply operation leads to exponential blow up of the resulting model, we identify a special restricted case where the Apply operation can be carried out efficiently. We introduce a relaxed version of Structured Decision \textsc{ dnnf} that we name Structured $\wedge_d$-\textsc{ fbdd} and demonstrate that this model is quite powerful for \textsc{ cnf}s of bounded incidence treewidth.
Categories: cs.CC