Document Type
Technical Report
Publication Date
1992-07-21
Technical Report Number
WUCS-92-26
Abstract
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.
Recommended Citation
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.
https://openscholarship.wustl.edu/cse_research/589
COinS
Comments
Permanent URL: http://dx.doi.org/10.7936/K7XK8CX5