3 papers
quant-ph2000
Quantum Finite State Transducers
R. Freivalds, A. Winter
We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite stat…
quant-ph1999
Probabilities to accept languages by quantum finite automata
Andris Ambainis, Richard Bonner, Rusins Freivalds +1
We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the c…
quant-ph1998
1-way quantum finite automata: strengths, weaknesses and generalizations
A. Ambainis, R. Freivalds
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a…