Knowledge Compilation Properties of Trees-of-BDDs, Revisited

Recent results have shown the interest of trees-of-BDDs as a suitable target language for propositional knowledge compilation from the practical side. In the present paper, the concept of tree-of-BDDs is extended to additional classes of data structures C, thus leading to trees-of-C representations (ToC). We provide a number of generic results enabling one to determine the queries/transformations satisfied by ToC depending on those satisfied by C. We also present some results about the spatial efficiency of the ToC languages. Focusing on the ToB language (and other related languages), we address a number of issues that remained open in (Subbarayan et al 2007). We show that beyond co and va, the ToB fragment satisfies im and me but satisfies neither cd nor any query among ce, se unlesssf P = NP. Among other results, we prove that ToB is not comparable w.r.t. succinctness with any of cnf, dnf, Dnnf unless the polynomial hierarchy collapses.This contributes to the explanation of some empirical results reported in (Subbarayan et al 2007).

Hélène Fargier, Pierre Marquis