Lifting query complexity to time-space complexity for two-way finite automata.
Shenggen ZhengYaqiao LiMinghua PanJozef GruskaLvzhou LiPublished in: CoRR (2023)
Keyphrases
- finite automata
- space complexity
- query complexity
- data complexity
- membership queries
- regular expressions
- arc consistency
- tree automata
- worst case
- wavelet transform
- grammatical inference
- resource consumption
- exact learning
- vc dimension
- concept class
- hidden markov models
- query evaluation
- learning algorithm
- dnf formulas
- databases
- worst case time complexity
- uniform distribution
- conjunctive queries
- query answering
- query language