Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings
This work addresses the challenge of efficient knowledge representation and reasoning in AI, particularly for Boolean functions, but it appears incremental as it builds on and generalizes existing compilation languages.
The paper tackles the problem of representing Boolean functions efficiently by introducing backdoor decomposable monotone circuits (BDMCs) that generalize existing concepts like DNNFs and backdoor trees, and shows that PC-BDMCs are polynomially equivalent to propagation complete (PC) encodings, enabling efficient operations in knowledge compilation.
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 $\mathcal{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 $\mathcal{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.