Campus Event Calendar
Event Entry
What and Who
Berge Multiplication for Monotone Boolean Dualization
Kazuhisa Makino
Department of Mathematical Informatics, University of Tokyo, Japan
Talk
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 5 March 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Given the prime CNF representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, the dualization problem calls for finding the corresponding prime DNF representation $\psi$ of $f$.
A very simple method (called {\em Berge multiplication} works by multiplying out the clauses of $\phi$ from left to right in some order, simplifying whenever possible using {\it the absorption law}.
We show that for any monotone CNF $\phi$, 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.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 02/28/2008 11:22
Khaled Elbassioni, 02/28/2008 11:21 -- Created document.
Khaled Elbassioni, 02/28/2008 11:21 -- Created document.