Lifting query complexity to time-space complexity for two-way finite automata.
Shenggen ZhengYaqiao LiMinghua PanJozef GruskaLvzhou LiPublished in: J. Comput. Syst. Sci. (2024)
Keyphrases
- space complexity
- finite automata
- query complexity
- data complexity
- membership queries
- grammatical inference
- regular expressions
- wavelet transform
- worst case
- arc consistency
- tree automata
- exact learning
- expressive power
- concept class
- vc dimension
- resource consumption
- hidden markov models
- dnf formulas
- concept classes
- database
- uniform distribution
- learning theory
- reinforcement learning