Read-Twice DNF Formulas are Properly Learnable.
Krishnan PillaipakkamnattVijay RaghavanPublished in: Inf. Comput. (1995)
Keyphrases
- dnf formulas
- membership queries
- concept class
- upper and lower bounds
- uniform distribution
- boolean functions
- monotone dnf
- conjunctive queries
- randomly chosen
- learning theory
- equivalence queries
- truth table
- term dnf
- monotone dnf formulas
- concept classes
- query complexity
- equivalence and membership queries
- upper bound
- training data
- efficient learning
- integrity constraints
- np complete