Strong duality in horn minimization

Endre Boros; Ondřej Čepek; Kazuhisa Makino

doi:10.1007/978-3-662-55751-8_11

Strong duality in horn minimization

Endre Boros
, Ondřej Čepek
, Kazuhisa Makino

Rutgers Business School, Management & Information Systems

Rutgers, The State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	American English
Title of host publication	Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings
Editors	Marc Zeitoun, Ralf Klasing
Publisher	Springer Verlag
Pages	123-135
Number of pages	13
ISBN (Print)	9783662557501
DOIs	https://doi.org/10.1007/978-3-662-55751-8_11
State	Published - 2017
Event	21st International Symposium on Fundamentals of Computation Theory, FCT 2017 - Bordeaux, France Duration: Sep 11 2017 → Sep 13 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10472 LNCS

Other

Other	21st International Symposium on Fundamentals of Computation Theory, FCT 2017
Country/Territory	France
City	Bordeaux
Period	9/11/17 → 9/13/17

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-55751-8_11

Cite this

Boros, E., Čepek, O., & Makino, K. (2017). Strong duality in horn minimization. In M. Zeitoun, & R. Klasing (Eds.), Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings (pp. 123-135). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10472 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-55751-8_11

Boros, Endre ; Čepek, Ondřej ; Makino, Kazuhisa. / Strong duality in horn minimization. Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings. editor / Marc Zeitoun ; Ralf Klasing. Springer Verlag, 2017. pp. 123-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ba61cf970e7f40ad97dd88c73f679367,

title = "Strong duality in horn minimization",

abstract = "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.",

author = "Endre Boros and Ond{\v r}ej {\v C}epek and Kazuhisa Makino",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag GmbH Germany 2017.; 21st International Symposium on Fundamentals of Computation Theory, FCT 2017 ; Conference date: 11-09-2017 Through 13-09-2017",

year = "2017",

doi = "10.1007/978-3-662-55751-8\_11",

language = "American English",

isbn = "9783662557501",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "123--135",

editor = "Marc Zeitoun and Ralf Klasing",

booktitle = "Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings",

address = "Germany",

}

Boros, E, Čepek, O & Makino, K 2017, Strong duality in horn minimization. in M Zeitoun & R Klasing (eds), Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10472 LNCS, Springer Verlag, pp. 123-135, 21st International Symposium on Fundamentals of Computation Theory, FCT 2017, Bordeaux, France, 9/11/17. https://doi.org/10.1007/978-3-662-55751-8_11

Strong duality in horn minimization. / Boros, Endre; Čepek, Ondřej; Makino, Kazuhisa.
Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings. ed. / Marc Zeitoun; Ralf Klasing. Springer Verlag, 2017. p. 123-135 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10472 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Strong duality in horn minimization

AU - Boros, Endre

AU - Čepek, Ondřej

AU - Makino, Kazuhisa

N1 - Publisher Copyright: © Springer-Verlag GmbH Germany 2017.

PY - 2017

Y1 - 2017

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

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

UR - https://www.scopus.com/pages/publications/85029407081

UR - https://www.scopus.com/pages/publications/85029407081#tab=citedBy

U2 - 10.1007/978-3-662-55751-8_11

DO - 10.1007/978-3-662-55751-8_11

M3 - Conference contribution

SN - 9783662557501

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 123

EP - 135

BT - Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings

A2 - Zeitoun, Marc

A2 - Klasing, Ralf

PB - Springer Verlag

T2 - 21st International Symposium on Fundamentals of Computation Theory, FCT 2017

Y2 - 11 September 2017 through 13 September 2017

ER -

Boros E, Čepek O, Makino K. Strong duality in horn minimization. In Zeitoun M, Klasing R, editors, Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings. Springer Verlag. 2017. p. 123-135. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-55751-8_11

Strong duality in horn minimization

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this