Knowledge Compilation Properties of Tree-of-BDDs

Sathiamoorthy Subbarayan, Lucas Bordeaux, Youssef Hamadi

We present a CNF to Tree-of-BDDs (ToB) compiler with complexity at most exponential in the tree width. We then present algorithms for interesting queries on ToB. Although some of the presented query algorithms are in the worst case exponential in the tree width, our experiments show that ToB can answer non-trivial queries like clausal entailment in reasonable time for several realistic instances. While our ToB-tool compiles all the used 91 instances, d-DNNF compilation failed for 12 or 8 of them based on the decomposition heuristic used. Also, on the succeeded instances, a d-DNNF is up to 1000 times larger than the matching ToB. The ToB compilations are often an order of magnitude faster than the d-DNNF compilation. This makes ToB a quite interesting knowledge compilation form.

Subjects: 11. Knowledge Representation; 15.2 Constraint Satisfaction

Submitted: Apr 17, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.