Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings

0536431 - ÚI 2022 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Kučera, P. - Savický, Petr
Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings.
Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2021, s. 3832-3840. ISBN 978-1-57735-866-4.
[AAAI 2021. Conference on Artificial Intelligence /35./. Vancouver / Online (CA), 02.02.2021-09.02.2021]
Grant CEP: GA ČR(CZ) GA19-19463S
Institucionální podpora: RVO:67985807
Klíčová slova: Satisfiability * Knowledge Representation Languages
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://ojs.aaai.org/index.php/AAAI/article/view/16501

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.
Trvalý link: http://hdl.handle.net/11104/0314209