|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
Quantum versus Probabilistic One-Way Finite Automata with Counter
by Richard Bonner, Rusins Freivalds and Maksim Kravtsev
Abstract:
The paper adds the one-counter one-way finite automaton
to the list of classical computing devices having quantum counterparts
more powerful in some cases. Specifically, two languages are considered,
the first is not recognizable by deterministic one-counter one-way finite
automata, the second is not recognizable with bounded error by proba-
bilistic one-counter one-way finite automata, but each recognizable with
bounded error by a quantum one-counter one-way finite automaton. This
result contrasts the case of one-way finite automata without counter,
where it is known that the quantum device is actually less powerful
than its classical counterpart.