Strong Duality in Horn Minimization
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10371729" target="_blank" >RIV/00216208:11320/17:10371729 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-662-55751-8_11" target="_blank" >http://dx.doi.org/10.1007/978-3-662-55751-8_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-55751-8_11" target="_blank" >10.1007/978-3-662-55751-8_11</a>
Alternative languages
Result language
angličtina
Original language name
Strong Duality in Horn Minimization
Original language description
A pure Horn CNF is minimal if no shorter pure Horn CNF representing the same function exists, where the CNF length may mean several different things, e.g. the number of clauses, or the total number of literals (sum of clause lengths), or the number of distinct bodies (source sets). The corresponding minimization problems (a different problem for each measure of the CNF size) appear not only in the Boolean context, but also as problems on directed hypergraphs or problems on closure systems. While minimizing the number of clauses or the total number of literals is computationally very hard, minimizing the number of distinct bodies is polynomial time solvable. There are several algorithms in the literature solving this task. In this paper we provide a structural result for this body minimization problem. We develop a lower bound for the number of bodies in any CNF representing the same Boolean function as the input CNF, and then prove a strong duality result showing that such a lower bound is always tight. This in turn gives a simple sufficient condition for body minimality of a pure Horn CNF, yielding a conceptually simpler minimization algorithm compared to the existing ones, which matches the time complexity of the fastest currently known algorithm.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA15-15511S" target="_blank" >GA15-15511S: Boolean techniques in knowledge representation</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
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
Article name in the collection
Fundamentals of Computation Theory, 21st International Symposium, FCT 2017
ISBN
978-3-662-55750-1
ISSN
0302-9743
e-ISSN
neuvedeno
Number of pages
13
Pages from-to
123-135
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Bordeaux, France
Event date
Sep 11, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—