Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00536431" target="_blank" >RIV/67985807:_____/21:00536431 - isvavai.cz</a>
Result on the web
<a href="https://ojs.aaai.org/index.php/AAAI/article/view/16501" target="_blank" >https://ojs.aaai.org/index.php/AAAI/article/view/16501</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-19463S" target="_blank" >GA19-19463S: Boolean Representation Languages Complete for Unit Propagation</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the AAAI Conference on Artificial Intelligence
ISBN
978-1-57735-866-4
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
3832-3840
Publisher name
AAAI Press
Place of publication
Palo Alto
Event location
Vancouver / Online
Event date
Feb 2, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000680423503105