Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings

Petr Kučera; Petr Savický

AAAI 2021technical3 citations

Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings

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.

BibTeX

@inproceedings{aaai2021_backdoordecompos,
  title = {Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings},
  author = {Petr Kučera and Petr Savický},
  booktitle = {AAAI 2021},
  year = {2021}
}