The shortest disjunctive normal form of a random Boolean function.

Nicholas Pippenger

Published in: Random Struct. Algorithms (2003)

Keyphrases

boolean functions
disjunctive normal form
randomly generated
decision rules
normal form
uniform distribution
classification rules
membership queries
conjunctive normal form
term dnf
learning dnf
rough sets
multi valued
binary decision diagrams