Learning monotone log-term DNF formulas
Yoshifumi Sakai, Akira Maruoka · 1994
Based on the uniform distribution PAC learning model, the learnability for monotone disjunctive normal form formulas with at most $O(\log n)$ terms ( $O(\log n)$ -term MDNF) is investigated.Using the technique of restriction, an algorithm that learns $O(\log n)$ -term MDNF in polynomial time is given.