Propagation Complete Encodings of Smooth DNNF Theories

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216208:11320/22:10452224

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Propagation Complete Encodings of Smooth DNNF Theories

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Propagation Complete Encodings of Smooth DNNF Theories

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA19-19463S" target="_blank" >GA19-19463S: Reprezentace booleovských funkcí úplné vzhledem k jednotkové propagaci</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Constraints

ISSN

1383-7133

e-ISSN

1572-9354

Svazek periodika

27

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

33

Strana od-do

327-359

Kód UT WoS článku

000805699300002

EID výsledku v databázi Scopus

2-s2.0-85131328469