A Quantum Query Complexity Trichotomy for Regular Languages.
Scott AaronsonDaniel GrierLuke SchaefferPublished in: CoRR (2018)
Keyphrases
- regular languages
- query complexity
- equivalence queries
- membership queries
- pac learning
- grammatical inference
- efficient learning
- exact learning
- regular expressions
- concept class
- uniform distribution
- decision problems
- finite automata
- context free grammars
- dnf formulas
- learning algorithm
- concept classes
- boolean functions
- target concept
- vc dimension
- tree patterns
- pattern languages
- statistical queries
- inductive inference
- learning theory
- upper bound
- lower bound