Knowledge Compilation Properties of Trees-of-BDDs, Revisited

Hélène Fargier (1, 2) , Pierre Marquis (3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CNRS - Centre National de la Recherche Scientifique
3 CRIL - Centre de Recherche en Informatique de Lens

Recent results have shown the interest of trees-of-BDDs [Subbarayan et al., 2007] 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 ToOBDD< 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 ToOBDD< fragment satisfies IM and ME but satisfies neither CD nor any query among CE, SE unless P = NP. Among other results, we prove that ToOBDD< 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].

Domaines: Intelligence artificielle [cs.AI]

Hélène Fargier, Pierre Marquis. Knowledge Compilation Properties of Trees-of-BDDs, Revisited. 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), The International Joint Conferences on Artificial Intelligence (IJCAI); The Association for the Advancement of Artificial Intelligence (AAAI), 2009, Pasadena, United States. pp.772-777. ⟨hal-00866834⟩