Proceedings

Knowledge Compilation Properties of Trees-of-BDDs, Revisited

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 772-776.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

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

  1. [Cadoli and Donini, 1998] M. Cadoli and F.M. Donini. A survey on knowledge compilation. AI Communications, 10(3-4):137-150, 1998.
  2. [Darwiche and Marquis, 2002] A. Darwiche and P. Marquis. A knowledge compilation map. Journal of Artificial Intel- ligence Research, 17:229-264, 2002.
  3. [Darwiche, 2001] A. Darwiche. Decomposable negation normal form. Journal of the ACM, 48(4):608-647, 2001.
  4. A. del Val. Tractable databases: How to make propositional unit resolution complete through com- pilation. In Proc. of KR'94, pages 551-561, 1994.
  5. [Fargier and Marquis, 2006] H. Fargier and P. Marquis. On the use of partially ordered decision graphs in knowledge compilation and quantified Boolean formulae. In Proc. of AAAI'06, pages 42-47, 2006.
  6. [Fargier and Marquis, 2008a] H. Fargier and P. Marquis. Ex- tending the knowledge compilation map: Closure princi- ples. In Proc. of ECAI'08, pages 50-54, 2008.
  7. [Fargier and Marquis, 2008b] H. Fargier and P. Marquis. Ex- tending the knowledge compilation map: Krom, Horn, affine and beyond. In Proc. of AAAI'08, pages 442-447, 2008.
  8. [Gogic et al., 1995] G. Gogic, H.A. Kautz, Ch.H. Papadim- itriou, and B. Selman. The comparative linguistics of knowledge representation. In Proc. of IJCAI'95, pages 862-869, 1995. IJCAI
  9. [Marquis, 2008] P. Marquis. Knowledge compilation: a sightseeing tour. In Tutorial notes, ECAI'08, 2008. avail- able on-line.
  10. [Pipatsrisawat and Darwiche, 2008] K. Pipatsrisawat and A. Darwiche. New compilation languages based on structured decomposability. In Proc. of AAAI'08, pages 517-522, 2008.
  11. [Selman and Kautz, 1996] B. Selman and H.A. Kautz. Knowledge compilation and theory approximation. Jour- nal of the ACM, 43:193-224, 1996.
  12. [Subbarayan et al., 2007] S. Subbarayan, L. Bordeaux, and Y. Hamadi. Knowledge compilation properties of tree-of- BDDs. In Proc. of AAAI'07, pages 502-507, 2007.
  13. [Wachter and Haenni, 2006] M. Wachter and R. Haenni. Propositional DAGs: A new graph-based language for rep- resenting Boolean functions. In Proc. of KR'06, pages 277-285, 2006.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards