Technical Report Number
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.
Goldman, Sally A. and Mathais, H. David, "Learning k-term DNF Formulas with an Incomplete Oracle" Report Number: WUCS-92-26 (1992). All Computer Science and Engineering Research.