-DNF Formulas from Membership Queries.
Francesco BergadanoDario CatalanoStefano VarricchioPublished in: STOC (1996)
Keyphrases
- dnf formulas
- membership queries
- uniform distribution
- exact learning
- equivalence queries
- monotone dnf
- concept class
- boolean functions
- learning algorithm
- efficient learning
- target concept
- pac learning
- query complexity
- monotone dnf formulas
- version space
- upper and lower bounds
- concept classes
- membership and equivalence queries
- read once formulas
- term dnf
- agnostic learning
- truth table
- dnf formulae
- integrity constraints
- lower bound