Left-to-right multiplication for monotone Boolean dualization

Endre Boros, Khaled Elbassioni, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)3424-3439
Number of pages16
JournalSIAM Journal on Computing
Issue number7
StatePublished - 2010

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


  • Dualization
  • Enumerating minimal hypergraph transversals
  • Monotone Boolean function


Dive into the research topics of 'Left-to-right multiplication for monotone Boolean dualization'. Together they form a unique fingerprint.

Cite this