Learning k-term DNF Formulas with an Incomplete Oracle
Sally A. Goldman · Open Scholarship Institutional Repository (Washington University in St. Louis) · 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 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.