On Minimum Representations of Matched Formulas (Extended Abstract)
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368723" target="_blank" >RIV/00216208:11320/17:10368723 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.24963/ijcai.2017/706" target="_blank" >http://dx.doi.org/10.24963/ijcai.2017/706</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.24963/ijcai.2017/706" target="_blank" >10.24963/ijcai.2017/706</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Minimum Representations of Matched Formulas (Extended Abstract)
Popis výsledku v původním jazyce
A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural - we show that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.
Název v anglickém jazyce
On Minimum Representations of Matched Formulas (Extended Abstract)
Popis výsledku anglicky
A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural - we show that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA15-15511S" target="_blank" >GA15-15511S: Booleovské techniky v reprezentaci znalostí</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2017
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
ISBN
978-0-9992411-0-3
ISSN
1045-0823
e-ISSN
neuvedeno
Počet stran výsledku
5
Strana od-do
4980-4984
Název nakladatele
International Joint Conferences on Artificial Intelligence
Místo vydání
Australia
Místo konání akce
Melbourne; Australia
Datum konání akce
19. 8. 2017
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—