Knowledge Compilation for Model Counting: Affine Decision Trees

Koriche, Frédéric; Lagniez, Jean-Marie; Marquis, Pierre; Thomas, Samuel

Knowledge Compilation for Model Counting: Affine Decision Trees

Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis, Samuel Thomas

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 947-952.

Abstract

Counting the models of a propositional formula is a key issue for a number of AI problems, but few propositional languages offer the possibility to count models efficiently. In order to fill the gap, we introduce the language EADT of (extended) affine decision trees. An extended affine decision tree simply is a tree with affine decision nodes and some specific decomposable conjunction or disjunction nodes. Unlike standard decision trees, the decision nodes of an EADT formula are not labeled by variables but by affine clauses. We study EADT, and several subsets of it along the lines of the knowledge compilation map. We also describe a CNF-to-EADT compiler and present some experimental results. Those results show that the EADT compilation-based approach is competitive with (and in some cases is able to outperform) the model counter Cachet and the d-DNNF compilation-based approach to model counting.

Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis, and Samuel Thomas. 2013. Knowledge Compilation for Model Counting: Affine Decision Trees. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 947–952. https://ijcai.org/proceedings/2013/145

@inproceedings{ijcai2013p145,
  title     = {Knowledge Compilation for Model Counting: Affine Decision Trees},
  author    = {Koriche, Frédéric and Lagniez, Jean-Marie and Marquis, Pierre and Thomas, Samuel},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {947--952},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/145},
}

TY  - CPAPER
TI  - Knowledge Compilation for Model Counting: Affine Decision Trees
AU  - Koriche, Frédéric
AU  - Lagniez, Jean-Marie
AU  - Marquis, Pierre
AU  - Thomas, Samuel
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 947
EP  - 952
UR  - https://ijcai.org/proceedings/2013/145
ER  -