Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings

No. 5: AAAI-21 Technical Tracks 5

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Constraint Satisfaction and Optimization

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.

10.1609/aaai.v35i5.16501