Learnability of DNF with representation-specific queries.
Liu YangAvrim BlumJaime G. CarbonellPublished in: ITCS (2013)
Keyphrases
- dnf formulas
- exact learning
- boolean functions
- equivalence queries
- membership queries
- uniform distribution
- learning algorithm
- response time
- pac learning
- query language
- query processing
- database
- pattern languages
- disjunctive normal form
- web search engines
- monotone dnf
- database queries
- user queries
- target concept
- efficient learning
- information retrieval systems
- binary decision diagrams
- query complexity
- monotone dnf formulas