Proceedings

Circuit-Aware d-DNNF Compilation

Vincent Derkinderen, Jean-Marie Lagniez

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4454-4462.

https://doi.org/10.24963/ijcai.2025/496

Keywords

  • Knowledge Representation and Reasoning: KRR: Knowledge compilation
  • Uncertainty in AI: UAI: Tractable probabilistic models

Abstract

Boolean circuits in d-DNNF (determinstic Decomposable Negation Normal Form) enable tractable probabilistic inference, motivating research into compilers that transform arbitrary Boolean circuit into this form. However, d-DNNF compilers commonly require the input to be in conjunctive normal form (CNF), which means that a user must first convert their Boolean circuit into CNF. In this work, we argue that d-DNNF compilation would substantially benefit from reasoning over the original input circuit's structure, rather than solely relying on its CNF representation. To this end, we adapt an existing compiler and implement an optimisation that becomes more readily available once we reason over the input circuit: the identification and elimination of don't care variables. We empirically demonstrate the effectiveness of this approach, achieving a significant improvement in both the number of solved instances and the size of the resulting circuits.

Vincent Derkinderen, and Jean-Marie Lagniez. 2025. Circuit-Aware d-DNNF Compilation. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4454–4462. https://doi.org/10.24963/ijcai.2025/496
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards