Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines.

Zachary Remscrim

Published in: ITCS (2021)

Keyphrases

finite automata
lower bound
turing machine
quantum computing
regular expressions
probabilistic automata
upper bound
grammatical inference
database systems
tree automata
deterministic automata
objective function
pattern matching