On Berge multiplication for monotone Boolean dualization

Endre Boros, Khaled Elbassioni, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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.

Original languageBritish English
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages48-59
Number of pages12
EditionPART 1
DOIs
StatePublished - 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: 7 Jul 200811 Jul 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/TerritoryIceland
CityReykjavik
Period7/07/0811/07/08

Fingerprint

Dive into the research topics of 'On Berge multiplication for monotone Boolean dualization'. Together they form a unique fingerprint.

Cite this