Complexity Issues Related to Propagation Completeness
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10144056" target="_blank" >RIV/00216208:11320/13:10144056 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.ipl.2013.07.001" target="_blank" >http://dx.doi.org/10.1016/j.ipl.2013.07.001</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.artint.2013.07.006" target="_blank" >10.1016/j.artint.2013.07.006</a>
Alternative languages
Result language
angličtina
Original language name
Complexity Issues Related to Propagation Completeness
Original language description
Knowledge compilation is a process of adding more information to a knowledge base in order to make it easier to deduce facts from the compiled base than from the original one. One type of knowledge compilation occurs when the knowledge in question is represented by a Boolean formula in conjunctive normal form (CNF). The goal of knowledge compilation in this case is to add clauses to the input CNF until a logically equivalent propagation complete CNF is obtained. A CNF is called propagation complete if after any partial substitution of truth values all logically entailed literals can be inferred from the resulting CNF formula by unit propagation. The key to this type of knowledge compilation is the ability to generate so-called empowering clauses. A clause is empowering for a CNF if it is an implicate and for some partial substitution of truth values it enlarges the set of entailed literals inferable by unit propagation. In this paper we study several complexity issues related to empowe
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Knowledge Techniques in Scheduling</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
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
Name of the periodical
Artificial Intelligence
ISSN
0004-3702
e-ISSN
—
Volume of the periodical
203
Issue of the periodical within the volume
říjen
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
16
Pages from-to
19-34
UT code for WoS article
000325196000002
EID of the result in the Scopus database
—