Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings

Autor:	Kučera, Petr, Savický, Petr
Rok vydání:	2018
Předmět:	Computer Science - Artificial Intelligence Computer Science - Logic in Computer Science 68T30 F.2.2
Druh dokumentu:	Working Paper
Popis:	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. Comment: The paper was significantly rewritten to improve readability, it is now an extended version of the paper accepted to AAAI 2021
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1811.09435 Zobrazit plný text záznamu View this record from Arxiv