Prediction-Preserving Reducibility with Membership Queries on Formal Languages.
Kouichi HirataHiroshi SakamotoPublished in: FCT (2001)
Keyphrases
- membership queries
- formal languages
- pattern languages
- exact learning
- dnf formulas
- uniform distribution
- equivalence queries
- query complexity
- boolean functions
- pac learning
- efficient learning
- learning algorithm
- context free grammars
- natural language
- read once formulas
- membership and equivalence queries
- monotone dnf formulas
- formal language
- concept classes
- monotone dnf
- integrity constraints
- databases
- database