ECCC-Report TR05-023https://eccc.weizmann.ac.il/report/2005/023Comments and Revisions published for TR05-023en-usMon, 21 Feb 2005 16:41:14 +0200
Paper TR05-023
| On k-term DNF with largest number of prime implicants |
Robert H. Sloan,
Balázs Szörényi,
György Turán
https://eccc.weizmann.ac.il/report/2005/023It 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.
Mon, 21 Feb 2005 16:41:14 +0200https://eccc.weizmann.ac.il/report/2005/023