On the Learnability of Boolean Formulae
Michael J. KearnsMing LiLeonard PittLeslie G. ValiantPublished in: STOC (1987)
Keyphrases
- boolean formulae
- term dnf
- boolean functions
- phase transition
- expressive power
- boolean variables
- pattern languages
- learning algorithm
- dnf formulas
- pac learning
- conjunctive normal form
- pac learnability
- uniform distribution
- membership queries
- decision lists
- equivalence queries
- disjunctive normal form
- inductive inference
- inductive logic programming
- orders of magnitude