On the Role of Canonicity in Knowledge Compilation


  • Guy Van den Broeck University of California, Los Angeles
  • Adnan Darwiche University of California, Los Angeles




knowledge compilation, sentential decision diagrams, decision diagrams


Knowledge compilation is a powerful reasoning paradigm with many applications across AI and computer science more broadly. We consider the problem of bottom-up compilation of knowledge bases, which is usually predicated on the existence of a polytime function for combining compilations using Boolean operators (usually called an Apply function). While such a polytime Apply function is known to exist for certain languages (e.g., OBDDs) and not exist for others (e.g., DNNFs), its existence for certain languages remains unknown. Among the latter is the recently introduced language of Sentential Decision Diagrams (SDDs): while a polytime Apply function exists for SDDs, it was unknown whether such a function exists for the important subset of compressed SDDs which are canonical. We resolve this open question in this paper and consider some of its theoretical and practical implications. Some of the findings we report question the common wisdom on the relationship between bottom-up compilation, language canonicity and the complexity of the Apply function.




How to Cite

Van den Broeck, G., & Darwiche, A. (2015). On the Role of Canonicity in Knowledge Compilation. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9423



AAAI Technical Track: Knowledge Representation and Reasoning