ML Anthology

Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings

Petr Kucera, Petr Savický
AAAI 2021 pp. 3832-3840
doi:10.1609/AAAI.V35I5.16501 /aaai/2021/kucera2021aaai-backdoor/

Abstract

We describe a compilation language of backdoor decomposable monotone circuits (BDMCs) which generalizes several concepts appearing in the literature, e.g. DNNFs and backdoor trees. A C-BDMC sentence is a monotone circuit which satisfies decomposability property (such as in DNNF) in which the inputs (or leaves) are associated with CNF encodings from a given base class C. We consider the class of propagation complete (PC) encodings as a base class and we show that PC-BDMCs are polynomially equivalent to PC encodings. Additionally, we use this to determine the properties of PC-BDMCs and PC encodings with respect to the knowledge compilation map including the list of efficient operations on the languages.

PDF AAAI Semantic Scholar

Cite

Text

Kucera and Savický. "Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I5.16501

Markdown

[Kucera and Savický. "Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/kucera2021aaai-backdoor/) doi:10.1609/AAAI.V35I5.16501

BibTeX

@inproceedings{kucera2021aaai-backdoor,
  title     = {{Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings}},
  author    = {Kucera, Petr and Savický, Petr},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {3832-3840},
  doi       = {10.1609/AAAI.V35I5.16501},
  url       = {https://mlanthology.org/aaai/2021/kucera2021aaai-backdoor/}
}