Exact Learning of Read-K Disjoint DNF and Not-so-Disjoint DNF

Abstract

A polynomial-time algorithm is presented for exactly learning the class of read-k disjoint DNF formulas—boolean formulas in disjunctive normal form where each variable appears at most k) and every assignment to the variables satisfies at most one term of F. The (standard) protocol used allows the learning algorithm to query whether a given assignment of boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned. We show that this result also applies for a generalization of read-k disjoint DNF which we call read-k sat-j DNF; these are DNF formulas in which every variable appears at most k times and every assignment satisfies at most j terms.