Learning k -term DNF formulas with an incomplete membership oracle
Sally A. Goldman, H. David Mathias · 1992
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 that this model can be applied to non-monotone classes. Namely, we describe a polynomial-time algorithm that constructs a k-term DNF formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of DNF formulas.