Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-023 | 16th February 2005 00:00

On k-term DNF with largest number of prime implicants

RSS-Feed




TR05-023
Authors: Robert H. Sloan, Balázs Szörényi, György Turán
Publication: 21st February 2005 16:41
Downloads: 3906
Keywords: 


Abstract:

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating decision tree with literals assigned to the leaves in a certain way. We also mention some related results and open problems.



ISSN 1433-8092 | Imprint