Learning k-term DNF Formulas with an Incomplete Oracle

Sally A. Goldman, Washington University in St Louis
H. David Mathais, Washington University in St Louis


We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate the this model can be applied to non-monotone classes. Namely, we describe a polynomial algorithm that exactly identifies a k-term DNF formula with a k-term DNF hypothesis using incomplete membership queries and equivalence queries from the class of DNF formulas.