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