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