Document Type

Technical Report

Publication Date

1992-07-21

Filename

WUCS-92-26.pdf

DOI:

10.7936/K7XK8CX5

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7XK8CX5

Download

Share

COinS