TY - GEN

T1 - On Berge multiplication for monotone Boolean dualization

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

N1 - Funding Information:
The first author is thankful for the partial support by NSF (CBET-0735910). The second and third authors thank the partial support by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science.

PY - 2008

Y1 - 2008

N2 - Given the prime CNF representation φ of a monotone Boolean function f : {0,1}n → {0,1}, the dualization problem calls for finding the corresponding prime DNF representation ψ of f. A very simple method (called Berge multiplication [2] [Page 52-53]) works by multiplying out the clauses of φ from left to right in some order, simplifying whenever possible using the absorption law. We show that for any monotone CNF φ, Berge multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNF's such as CNF's with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.

AB - Given the prime CNF representation φ of a monotone Boolean function f : {0,1}n → {0,1}, the dualization problem calls for finding the corresponding prime DNF representation ψ of f. A very simple method (called Berge multiplication [2] [Page 52-53]) works by multiplying out the clauses of φ from left to right in some order, simplifying whenever possible using the absorption law. We show that for any monotone CNF φ, Berge multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNF's such as CNF's with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=49049115164&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70575-8_5

DO - 10.1007/978-3-540-70575-8_5

M3 - Conference contribution

AN - SCOPUS:49049115164

SN - 3540705740

SN - 9783540705741

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

SP - 48

EP - 59

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -