Propagation Complete Encodings of Smooth DNNF Theories

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F22%3A00559241" target="_blank" >RIV/67985807:_____/22:00559241 - isvavai.cz</a>

Alternative codes found

RIV/00216208:11320/22:10452224

Result on the web

<a href="https://dx.doi.org/10.1007/s10601-022-09331-2" target="_blank" >https://dx.doi.org/10.1007/s10601-022-09331-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10601-022-09331-2" target="_blank" >10.1007/s10601-022-09331-2</a>

Result language

angličtina

Original language name

Propagation Complete Encodings of Smooth DNNF Theories

Original language description

We investigate conjunctive normal form (CNF) encodings of a function represented with a decomposable negation normal form (DNNF). Several encodings of DNNFs and decision diagrams were considered by (Abio et al., 2016). The authors differentiate between encodings which implement consistency or domain consistency by unit propagation from encodings which are unit refutation complete or propagation complete. The difference is that in the former case we do not care about propagation strength of the encoding with respect to the auxiliary variables while in the latter case we treat all variables (the main and the auxiliary ones) in the same way. The currently known encodings of DNNF theories implement domain consistency. Building on these encodings we generalize the result of (Abio et al., 2016) on a propagation complete encoding of decision diagrams and present a propagation complete encoding of a DNNF and its generalization for variables with finite domains.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Constraints

ISSN

1383-7133

e-ISSN

1572-9354

Volume of the periodical

27

Issue of the periodical within the volume

3

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

33

Pages from-to

327-359

UT code for WoS article

000805699300002

EID of the result in the Scopus database

2-s2.0-85131328469