Complexity Issues Related to Propagation Completeness

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity Issues Related to Propagation Completeness

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Complexity Issues Related to Propagation Completeness

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Znalostní techniky v rozvrhování</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

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

Artificial Intelligence

ISSN

0004-3702

e-ISSN

—

Svazek periodika

203

Číslo periodika v rámci svazku

říjen

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

19-34

Kód UT WoS článku

000325196000002

EID výsledku v databázi Scopus

—