Disjoint essential sets of implicates of a CQ Horn function

Result code in IS VaVaI

RIV/00216208:11320/11:10103934 - isvavai.cz

Result on the web

http://dx.doi.org/10.1007/s10472-011-9263-9

DOI - Digital Object Identifier

10.1007/s10472-011-9263-9

Result language

angličtina

Original language name

Disjoint essential sets of implicates of a CQ Horn function

Original language description

In this paper we study a class of CQ Horn functions introduced in Boros et al. (2010). We prove that given a CQ Horn function f, the maximal number of pairwise disjoint essential sets of implicates of f equals the minimum number of clauses in a CNF representing f. In other words, we prove that the maximum number of pairwise disjoint essential sets of implicates of f constitutes a tight lower bound on the size (the number of clauses) of any CNF representation of f.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2011

Confidentiality

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

Name of the periodical

Annals of Mathematics and Artificial Intelligence

ISSN

1012-2443

e-ISSN

—

Volume of the periodical

61

Issue of the periodical within the volume

3

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

14

Pages from-to

231-244

UT code for WoS article

000297588000005

EID of the result in the Scopus database

—