On Minimum Representations of Matched Formulas

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10285651" target="_blank" >RIV/00216208:11320/14:10285651 - isvavai.cz</a>

Výsledek na webu

<a href="http://jair.org/media/4517/live-4517-8363-jair.pdf" target="_blank" >http://jair.org/media/4517/live-4517-8363-jair.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1613/jair.4517" target="_blank" >10.1613/jair.4517</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Minimum Representations of Matched Formulas

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. Each matched CNF is trivially satisfiable (each clause can be satisfied by its representative variable). Another property which is easy to see, is that the class of matched CNFs is not closed under partial assignment of truth values to variables. This latter property leads to a fact (proved here) that given two matched CNFs it is co-NP complete to decide whether they are logically equivalent. The construction in this proof leads to another result: a much shorter and simpler proof of the fact that the Boolean minimization problem for matched CNFs is a complete problem for thesecond level of the polynomial hierarchy. The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF re

Název v anglickém jazyce

On Minimum Representations of Matched Formulas

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. Each matched CNF is trivially satisfiable (each clause can be satisfied by its representative variable). Another property which is easy to see, is that the class of matched CNFs is not closed under partial assignment of truth values to variables. This latter property leads to a fact (proved here) that given two matched CNFs it is co-NP complete to decide whether they are logically equivalent. The construction in this proof leads to another result: a much shorter and simpler proof of the fact that the Boolean minimization problem for matched CNFs is a complete problem for thesecond level of the polynomial hierarchy. The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF re

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

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

Journal of Artificial Intelligence Research

ISSN

1076-9757

e-ISSN

—

Svazek periodika

51

Číslo periodika v rámci svazku

12/2014

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

17

Strana od-do

707-723

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—